欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

(二分)51nod 1128 正整数分组 V2

程序员文章站 2022-03-14 19:21:02
...

给出一个长度为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。因此第一种方案更优。并且第一种方案的最大值是所有方案中最小的。输出这个最小的最大值。

输入

第1行:2个数N, K,中间用空格分隔,N为数组的长度,K为要分为多少组。(2 <= K < N <= 50000)
第2 - N + 1行:数组元素(1 <= A[i] <= 10^9)

输出

输出这个最小的最大值。

输入样例

6 3
1
2
3
4
5
6

输出样例

9

二分答案

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
ll n,k,a[maxn];
bool work(ll x)
{
    ll c=0;
    ll sum=0;
    for(ll i=0;i<n;i++)
    {
        if((sum+a[i])>x)
        {
            sum=0;
            c++;
        }
        sum+=a[i];
        if(c>k) return false;
    }
    if(sum) c++;
    if(c>k) return false;
    else return true;

}
int main()
{
    scanf("%lld%lld",&n,&k);
    ll l=0,r=0,key;
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
        r+=a[i]; if(a[i]>l) {l=a[i];key=i;}
    }
    while(r>l)
    {
        ll mid=l+r>>1;
        if(work(mid))
            r=mid;
        else l=mid+1;
    }
    printf("%lld",l);
    return 0;
}