好贷网好贷款

codeforces 191 E (树状数组+二分)

发布时间:2016-12-3 23:53:30 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"codeforces 191 E (树状数组+二分)",主要涉及到codeforces 191 E (树状数组+二分)方面的内容,对于codeforces 191 E (树状数组+二分)感兴趣的同学可以参考一下。

转自:http://www.cnblogs.com/wuyiqi/archive/2012/06/01/2531301.html 题意,给你n个数,让你求第k大的连续区间和是多少 例如 3 4 1 4 2 最大的区间和 1 4 2 第二大         4 2 第三大         1 4 第四大即答案 4 首先要看出单调性:枚举的和越大,区间和大于它的区间数就越少 所以可以采用二分+树状数组统计的方法 二分答案,再n * log(n)判断有几个区间的区间和大于mid,然后调整上下界,使这个值不断的接近k。 判断符合条件的区间总数:线性扫描s【】(前n项和)  每次判断以i结尾的区间有几个区间和大于等于mid,累加即可  wuyiqi(593572013) 15:02:43  O(n)扫描过去吧,复杂度是nlognlongn wuyiqi(593572013) 15:03:05  我没看错题吧。。 御坂#???(826513189) 15:03:09  没有 hill(120482051) 15:03:14  怎么算的呀 求详细 我很弱 。。 御坂#???(826513189) 15:03:15  窝又想说,这个其实不用数据结构…… 御坂#???(826513189) 15:03:35  设s[i] = a[1] + a[2] + ... + a[i] 御坂#???(826513189) 15:03:46  就是求有多少j < i,满足s[i] - s[j] >= mid 御坂#???(826513189) 15:04:14  枚举i = 1, 2, ..., n,把[1..i - 1]的s[i]放到一个御坂树里面 hill(120482051) 15:04:40  御坂树 ForeverBell(545479001) 15:04:47  这是什么 御坂#???(826513189) 15:04:49  每次就是在御坂树里面查询s[j] <= s[i] - mid有多少个 wuyiqi(593572013) 15:04:57  。。。 追忆似风(81642410) 15:04:59  平衡树? 御坂#???(826513189) 15:05:06  至于什么是御坂树,可以选择你喜欢的任何支持这个的数据结构 追忆似风(81642410) 15:05:11  御坂#???(826513189) 15:05:12  比如说线段树,平衡树,树状数组 ForeverBell(545479001) 15:05:14  。。 御坂#???(826513189) 15:05:21  anyway,这题不用数据结构…… ForeverBell(545479001) 15:05:36  一个set+lower-bound不就行了么。。 御坂#???(826513189) 15:05:48  lower_bound没法数大小 ForeverBell(545479001) 15:05:54  噢 ForeverBell(545479001) 15:06:09  - - 御坂#???(826513189) 15:06:35  可以直接分治 御坂#???(826513189) 15:06:44  也是O(N log N)一次 #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define clr(x,what) memset(x,what,sizeof(x)); typedef __int64 lld; const int maxn = 100010; const lld inf = 1e9 ; int c[maxn]; lld s[maxn],num[maxn]; int n,tot; void update(int x,int d){ for(;x<maxn;x+=x&-x) c[x]+=d; } int sum(int x){ int ans=0; for(;x>0;x-=x&-x) ans+=c[x]; return ans; } lld calc(lld mid){ lld ans=0; clr(c,0); for(int i=1;i<=n;i++){ if(s[i]>=mid) ans++; lld x=s[i]-mid; int id=upper_bound(num+1,num+tot+1,x)-num-1; /*upper_bound原因是查询s[j] <= s[i] - mid,lower_bound返回如果相等好说 不相等的话返回的需要-1 upper_bound直接 返回大于s[i] - mid的值的位置 统统-1 就好。 */ int id2=lower_bound(num+1,num+tot+1,s[i])-num; ans+=sum(id); update(id2,1); } return ans; } int main(){ int i,j,k; lld m; scanf("%d%I64d",&n,&m); for(i=1;i<=n;i++){ scanf("%I64d",&s[i]); s[i]+=s[i-1]; num[i]=s[i]; //前缀和 } sort(num+1,num+n+1); tot=unique(num+1,num+n+1)-num-1; lld l=-inf*lld(n),r=inf*lld(n),mid,best=-1; while(l<=r){ mid=(l+r)/2; if(calc(mid)>=m){ best=mid; l=mid+1; } else r=mid-1; } printf("%I64d\n",best); return 0; }

上一篇:Win32 Series - Simple Use of the Clipboard
下一篇:Nodejs之require加载机制(模块可以污染全局空间)

相关文章

相关评论