51nod 1128 二分

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1128

1128 正整数分组 V2

基准时间限制：1 秒 空间限制：131072 KB 分值: 80 难度：5级算法题

收藏

关注

给出一个长度为N的正整数数组，不改变数组元素的顺序，将这N个数分为K组。各组中元素的和分别为S1,S2....Sk。如何分组，使得S1至Sk中的最大值最小？

例如：1 2 3 4 5 6分为3组，{1 2 3} {4 5} {6}，元素和为6, 9, 6，最大值为9。也可以分为{1 2 3 4} {5} {6}。元素和为：10 5 6，最大值为10。因此第一种方案更优。并且第一种方案的最大值是所有方案中最小的。输出这个最小的最大值。

Input

第1行：2个数N, K，中间用空格分隔，N为数组的长度，K为要分为多少组。(2 <= K < N <= 50000)

第2 - N + 1行：数组元素(1 <= A[i] <= 10^9)

Output

输出这个最小的最大值。

Input示例

6 3

1

2

3

4

5

6

Output示例

9
对答案进行二分找到最小值，判定这个值是否合法采用贪心法，在和不超过这个值得情况下一直累计计算最小能分成几个区间，如果区间数小于等于K说明当前值可行，否则不可。

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 int A[],N,K;

 bool ok(LL M)

 {

     LL s=,r=; int i=;

     for(r=;i<=N;r++,s=)

     {

         if(A[i]>M) return ;

         while(s+A[i]<=M&&i<=N){

             s+=A[i];

             i++;

         }

     }

     return r<=K;

 }

 int main()

 {

     int i,j,k;

     cin>>N>>K;

     for(i=;i<=N;++i) scanf("%d",A+i);

     LL l=,r=1e15;

     while(l<r){

         LL mid=l+(r-l)/;

         if(ok(mid)) r=mid;

         else l=mid+;

     }

     cout<<l<<endl;

     return ;

 }