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

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

程序员文章站 2022-03-14 19:28:26
...

基准时间限制:1 秒 空间限制:131072 KB 分值: 80
给出一个长度为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
思路:答案有单调性,且很好验证答案正确性O(n),所以剧二分好了
代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxx 50005
#define ll long long
using namespace std;
int a[maxx];
int n,k;
bool check(ll num)
{
    int _count=0;
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        if(sum+a[i]<=num)
            sum+=a[i];
        else
        {
            _count++;
            sum=a[i];
        }
    }
    if(sum>0)_count++;
    return _count<=k;
}
inline ll _max(ll a,ll b)
{
    return a>b?a:b;
}
int main()
{
    cin>>n>>k;
    ll L=0,R=0;
    int num=n/k+(num%k?1:0);
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        L=_max(L,(ll)a[i]);
        R+=a[i];
    }

    while(L<=R)
    {
        int mid=(L+R)>>1;
        if(check(mid))R=mid-1;
        else L=mid+1;
    }
    cout<<L<<endl;
    return 0;
}