本文共 1098 字，大约阅读时间需要 3 分钟。

1128 正整数分组 V2

题目

给出一个长度为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)

输出

输出这个最小的最大值。

输入样例

6 3

输出样例

9

代码

#include 
   
    #define ll long longusing namespace std;ll k, n, sum = 0, a[50010];void init() {
       cin >> n >> k;    for (int i = 0; i < n; ++i) {
           cin >> a[i];        sum += a[i];    }}ll com(ll key) {
       ll summ = 0;    ll kk = k;    for (int i = 0; i < n; i++) {
           if (summ + a[i] > key) {
               summ = a[i], kk--;        } else {
               summ += a[i];        }    }    return kk;}ll bin_search(ll a, ll b) {
       if (a == b - 1) {
           return b;    }    ll mid = (a + b) / 2;    if (com(mid) <= 0) {
           return bin_search(mid, b);    } else {
           return bin_search(a, mid);    }}int main() {
       init();    cout << bin_search(1, sum);    return 0;}
   

转载地址：https://blog.csdn.net/weixin_43820352/article/details/108186042 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！