首页 > 代码库 > 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 }思路：最近老师叫我刷分治，可是这个题我没看出分治来啊，先把读进来的数组每个值都减去ｍ（所以只让他大于0即可）并把它做成前缀和，用这个前缀和数组，归并排序，求一下逆序对。
Codevs 3324 新斯诺克
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。