工资（money）

(money/money.in/money.out)

时限1000ms 内存256MB

聪哥在暑假参加了打零工的活动，这个活动分为n个工作日，每个工作日的工资为Vi。有m个结算工钱的时间,聪哥可以自由安排这些时间，也就是说什么时候拿钱，老板说的不算，聪哥才有发言权！（因为聪哥是土豪，他是老板的老板）

聪哥不喜欢身上一次性有太多的钱，于是他想安排一下拿钱的时间，使他一次性拿的钱中最大的最小。（最后一天一定要领钱）

输入

第一行 2个数 n,m

接下来n行，每行一个数，代表Vi.

输出

最小的最大钱数。

样例输入

7 5

100

400

300

100

500

101

400

样例输出

500

样例说明

100 400//300 100//500//101//400//

“//”表示老大要去拿钱。

数据范围

20% 1<=n<=20

另 20% 1<=n<=50,Vi的和不超过1000

100% 1<=n<=100,000,m<=n,Vi<=10,000

做法：二分答案。

大概用了２０＋分钟。

代码：

 1 #include<cstdio>
 2 int n,m,l=1,r;
 3 int a,b,c;
 4 int s[100010];
 5 int main(){
 6     freopen("money.in","r",stdin);
 7     freopen("money.out","w",stdout);
 8     scanf("%d%d",&n,&m);m--;
 9     for(int i=1;i<=n;i++){
10         scanf("%d",&s[i]);
11         r+=s[i];
12     }
13     while(1){
14         if(l==r) break;
15         int mid=(l+r)>>1;a=b=0;
16         for(int i=1;i<=n;i++){
17             if(a+s[i]>mid){++b;a=s[i];}
18             else a+=s[i];
19         }
20         if(b>m) l=mid+1;
21         else r=mid;
22     }
23     printf("%d
",l);
24     return 0;
25 }

然而只得了90分，为什么呢？

他的数据不清真。说好的Vi<=10000呐！

我的r都溢出了好几遍。。。

数据的锅，我不背。