Codeforces Round #143 (Div. 2) C

http://codeforces.com/contest/231/problem/C

昨天的cf。比赛的时候其实有点思路的，但是因为B搞错方向了没敢写C。刚刚写了下，AC了。用的思路还真是昨天晚上的。囧。昨天晚上看的时候有一个地方不知道怎么转换，就是怎么快速求出i-->i+ans需要加多少个1.刚刚化了下。得到了：cnt=sum[i-1+m]-sum[i]-(i-1)*(a[i-1+m]-a[i])。sum[i]表示1-->i需要加多少个1使得1-->i都变为a[i]。自己写下就能得到上面那个式子。昨天就是这里没深入。

然后刚刚做的时候想到了 sum[]定义为__int64 觉得a数组应该不需要定义为__int64的。可是错了。改了后AC了。。不知道为啥。。。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #include <algorithm>
 6 #include <cmath>
 7 #include <stack>
 8 
 9 using namespace std;
10 
11 #define MAXN 100010
12 __int64 a[MAXN];
13 __int64 sum[MAXN];//前i个数加多少个数使得前i个数变为a[i]
14 int n,k;
15 
16 int main()
17 {
18     while(scanf("%d%d",&n,&k)  != EOF)
19     {
20         for(int i=1;i<=n;i++)
21             scanf("%I64d",&a[i]);
22         sort(a+1,a+n+1);
23         sum[0]=0;
24         sum[1]=0;
25         for(int i=2;i<=n;i++)
26             sum[i]=sum[i-1]+(i-1)*(a[i]-a[i-1]);
27         int ans;
28         int num;
29         int left=1,right=n;
30         while(left<=right)
31         {
32             int m=(left+right)>>1;
33             bool flag=0;
34             int i=1;
35             for(i=1;i-1+m<=n;i++)
36                 if(sum[i-1+m]-sum[i]-(i-1)*(a[i-1+m]-a[i])<=k)
37                 {
38                     flag=1;
39                     break;
40                 }
41             if(flag)
42             {    
43                 left=m+1;
44                 ans=m;
45                 num=a[i-1+m];
46             }
47             else
48                 right=m-1;
49         }
50         printf("%d %d\n",ans,num);
51     }
52     return 0;
53 }