/**//* 题意:给出n个数 问多少个区间,使得平均值>a n≤10^5 枚举左右指针可以知道多少个,但是O(n^2) TLE 枚举左右指针,找对数,不是跟逆序对很像?有O(nlogn)算法 设sum[i]=∑x[i]-a 若区间[i,j]平均值>a 则有 sum[j]-sum[i-1] = x[j]-a + x[j-1]-a + + x[i]-a>0 即sum[i]<sum[j] 所以问题转化为有多少对sum[i]<sum[j] ,i<j 由于可以是区间[1,j]满足条件,即sum[0]<sum[j] 所以加多一个sum[0]=0
*/ #include<cstdio> #include<cstring>
const int MAXN = 100010;
long long sum[MAXN]; long long _sum[MAXN];
long long merge(int beg,int end)//find sum[i]<sum[j] { long long ans = 0; int mid=(beg+end)>>1; int i=beg,j=mid+1,c=beg; while(i<=mid&&j<=end) { if(sum[i]>=sum[j])_sum[c++]=sum[i++]; else { ans+=(mid-i+1); _sum[c++]=sum[j++]; } } while(i<=mid)_sum[c++]=sum[i++]; while(j<=end)_sum[c++]=sum[j++]; while(beg<=end)sum[beg]=_sum[beg++]; return ans; } long long mergeSort(int beg,int end) { if(beg>=end)return 0; int mid=(beg+end)>>1; long long ans = 0; ans+=mergeSort(beg,mid); ans+=mergeSort(mid+1,end); ans+=merge(beg,end); return ans; } int main() { //freopen("in","r",stdin); int T,N,A; for(scanf("%d",&T);T--;) { scanf("%d%d",&N,&A); sum[0]=0; for(int i=1,x;i<=N;i++) { scanf("%d",&x); x-=A; sum[i]=sum[i-1]+x; } printf("%I64d\n",mergeSort(0,N)); } return 0; }
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|