首页 > 代码库 > Codevs 3324 新斯诺克

Codevs 3324 新斯诺克

 时间限制: 1 s   空间限制: 64000 KB   题目等级 : 白银 Silver 
题目描述 Description
现在考虑这样一种新斯诺克,设母球(母球即是白球,用于击打其他球)的标号为M,台面上有N 个红球排成一排,每一个红球都有一个标号,他们的标号代表了他们的分数。

现在用母球击打这些红球,一杆击打,如果母球接触到红球,就称为“K 到红球”。我们假设,一次可以击打任意多相邻连续的红球,也可以只击打一个球。并且红球既不会落袋,也不会相互发生碰撞,而只是停留在原处。每次击打时候,要想“K 到红球”,至少要击打一个红球,如果想一次击打多个红球,那么击打的红球必须是依次连续排列的。如果一次“K 到红球”所有红球的标号之和的平均数大于母球的标号M,就获得了一个“连击”。

现在请你计算总共能有多少种“连击”方案。

注意:如果当前有标号为1、2、3 的三种红球,母球标号为0,有如下6 种获得“连击”方案:( 1)、( 2)、( 3)、( 1,2)、( 2,3)、( 1,2,3)

输入描述 Input Description

共有两行。

第一行是N,M (N<=100000,M<=10000) ,N 表示台面上一共有N 个红球,M 表示母球的标号。

第二行是N 个正整数,依次表示台面上N 个红球的标号,所有标号均不超过10000。

输出描述 Output Description

只有一个数,为“连击”的方案总数。

样例输入 Sample Input

4 3

3 7 2 4

样例输出 Sample Output

7

数据范围及提示 Data Size & Hint

请看上面。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int n,m,a[100010]={0},b[100010]; 7 long long ans=0; 8 void ni(int l,int r) 9 {10     if(l>=r) return;11     int mid=(l+r)/2;12     ni(l,mid);ni(mid+1,r);13     int i=l,j=mid+1,k=l;14     while(i<=mid&&j<=r)15     {16         if(a[i]<a[j])17         {18             b[k++]=a[i++];19             ans+=r-j+1;20         }21         else{22             b[k++]=a[j++];23         }24     }25      while(i<=mid) b[k++]=a[i++];26      while(j<=r) b[k++]=a[j++];27      for(int w=l;w<=r;w++) a[w]=b[w];28 }29 int main()30 {31     scanf("%d%d",&n,&m);32     for(int i=1;i<=n;i++)33     { scanf("%d",&a[i]);a[i]=a[i]-m+a[i-1]; }34     ni(0,n);35     printf("%lld",ans);36     return 0;37 }

思路:最近老师叫我刷分治,可是这个题我没看出分治来啊,先把读进来的数组每个值都减去m(所以只让他大于0即可)并把它做成前缀和,用这个前缀和数组,归并排序,求一下逆序对。

Codevs 3324 新斯诺克