本文共 2144 字，大约阅读时间需要 7 分钟。
zzs和zzy正在被寒假作业折磨，然而他们有答案可以抄啊。
他们共有n项寒假作业。zzy给每项寒假作业都定义了一个疲劳值Ai，表示抄这个作业所要花的精力。zzs现在想要知道，有多少组连续的寒假作业的疲劳值的平均值不小于k？
简单地说，给定n个正整数A1,A2,A3,...,An，求出有多少个连续的子序列的平均值不小于k。
输入格式：
第一行两个正整数，n和k。
第二行到第n+1行，每行一个正整数Ai。
输出格式：
一个非负整数。
3 2123
4
样例解释：共有6个连续的子序列，分别是(1)、(2)、(3)、(1,2)、(2,3)、(1,2,3)，平均值分别为1、2、3、1.5、2.5、2，其中平均值不小于k的共有4个。
对于20%的数据，1<=n<=100；
对于50%的数据，1<=n<=5000；
对于100%的数据，1<=n<=100000；
对于100%的数据，1<=Ai<=10000，1<=k<=10000。
先来简化一下题意：给定一个数列a[]，求有多少个子序列元素平均值大于等于k。
遍历所有子区间复杂度最小O(n^2)，可用前缀和O(1)得到任意区间和。
想个办法吧，这类题要么用奇奇怪怪的数据结构(可能有这样的数据结构?我不知道)，要么推公式。
那就推公式——
首先取出一段区间吧，设1<=i<=j<=n，然后这段区间（a[i]~a[j]）的平均值为
(a[i]+a[i+1]+…+a[j]) / (j-i+1)>=k
分母不太好看，乘到右边吧——
a[i]+a[i+1]+…+a[j] >= k*(j-i+1)
a[i]+a[i+1]+…+a[j]>= k+…+k //(j-i+1)个k
接下来有点关键啦
a[i]+a[i+1]+…+a[j] - k-…-k>=0
(a[i]-k) + (a[i+1]-k) +……+ (a[j]-k)>=0//哦？那么整齐，有意思
那我们另设一个数组b[]，使b[i]=a[i]-k吧
b[i]+b[i+1]+…+b[j]>=0
哦？b[]的一段区间和大于等于零？
记得前面想暴力的时候说过用前缀和能O(1)取得任意区间和吗？给b[]套上区间和吧
设s[i]=b[1]+b[2]+b[3]+…+b[i]，特别的，令s[0]=0，那么b[i]+b[i+1]+…+b[j] = s[j]-s[i-1]。
s[j] - s[i-1]>=0
移项一下
s[j]>=s[i-1]，哇，快了。
因为之前定义过i<=j，所以i-1<j，这是什么？
是的没错！逆序对（大雾，应该叫顺序对的）！
i-1<j且s[i-1]<=s[j]，对s数组求逆序对顺序对即可。
不会的就先掌握这个姿势吧，也挺简单的。
最后说一下，我不知道为什么把求逆序对的程序类比着改一下，求出来“顺序对”就是对的，反正套上去就AC了，如果有那个dalao知道，能在评论区为本蒟蒻解惑吗？谢谢了。
#includeint n,k;int a[100010]={ 0},temp[100010]={ 0};long long ans=0;void merge(int s1,int e1,int s2,int e2){ int s=s1,e=e2,i=s1; while(s1<=e1&&s2<=e2) { if(a[s1]<=a[s2]) { ans+=e2-s2+1;//求逆序对在"a[s1]>a[s2]"里,求顺序对反过来 temp[i++]=a[s1++]; } else temp[i++]=a[s2++]; } while(s1<=e1) temp[i++]=a[s1++]; while(s2<=e2) temp[i++]=a[s2++]; for(i=s;i<=e;i++) a[i]=temp[i];}void msort(int l,int r){ if(l==r) return; int mid=(l+r)>>1; msort(l,mid); msort(mid+1,r); merge(l,mid,mid+1,r);}int main(){ scanf("%d%d",&n,&k); for(int i=1,b;i<=n;i++) { scanf("%d",&b); b-=k; a[i]=a[i-1]+b;//输入a[i]时就顺带处理出了s[i]，依然存在a[i]里 } msort(0,n); printf("%lld",ans); return 0;}
转载地址：http://jxfva.baihongyu.com/