【题目描述】
设母球（母球即是白球，用于击打其他球）的标号为M，台面上有N个红球排成一排，每一个红球都有一个标号，他们的标号代表了他们的分数。
现在用母球击打这些红球，一杆击打，如果母球接触到红球，就称为“K到红球”。我们假设，一次可以击打任意多相邻连续的红球，也可以只击打一个球。并且红球既不会落袋，也不会相互发生碰撞，而只是停留在原处。每次击打时候，要想“K到红球”，至少要击打一个红球，如果想一次击打多个红球，那么击打的红球必须是依次连续排列的。如果一次“K到红球”所有红球的标号之和的平均数大于母球的标号M，就获得了一个“连击”。
现在请你计算总共能有多少种“连击”方案。
注意：如果当前有标号为1、2、3的三种红球，母球标号为0，有如下6种获得“连击”方案：(1)、(2)、(3)、(1,2)、(2,3)、(1,2,3)。
【输入描述】
第一行输入N、M(N<=100000，M<=10000)，N表示台面上一共有N个红球，M表示母球的标号；
第二行输入N个正整数，依次表示台面上N 个红球的标号，所有标号均不超过10000。
【输出描述】
输出一个数，表示“连击”的方案总数。
【样例输入】
4 3
3 7 2 4
【样例输出】
7
源代码： #include<cstdio> int n,k,num(0); long long ans(0),i[100001],h[100001]; void x1(int t1,int t2) //归并排序求逆序对。 { if (t1==t2) return; x1(t1,(t1+t2)/2); x1((t1+t2)/2+1,t2); int x=t1,y=(t1+t2)/2+1,z=y-1,num=t1; while (x<=z&&y<=t2) if (i[x]<=i[y]) h[num++]=i[x++]; else { ans+=z-x+1; //因为在x[]与y[]之中，数皆为有序（单调不减），故后面的数一定也更大。 h[num++]=i[y++]; } while (x<=z) h[num++]=i[x++]; while (y<=t2) h[num++]=i[y++]; for (int a=t1;a<=t2;a++) i[a]=h[a]; } int main() { scanf("%d%d",&n,&k); i[0]=0; for (int a=1;a<=n;a++) { scanf("%d",&i[a]); num+=i[a]; i[a]=k*a-num; } x1(0,n); printf("%ld",ans); return 0; } /* 确实是一道不错的题。 乍一看似乎无从下手，但其实需要将其灵活地转化。 根据题意，无非是从所给的数列中找出相邻的、平均值大于k的、不同的子序列。 { 对于符合题意的子序列 [i+1,j]， 则有 (sum[j]-sum[i])/(j-i)>k， 即 sum[j]-(k*j)>sum[i]-(k*i)， 设 A[i]=sum[i]-(k*i)， 则以上可转化为 A[j]>A[i] (i<j)， 是为逆序对问题， 由于子序列表示为 [i+1,j]，所以归并范围为 [0,n]。 } */