一、题意

输入包含若干组数据。
每组数据输入一个n, k。然后输入一个长度为n的序列。
要求你把这个序列划分为k段，记每一段的数字和为S(i)，要求使得S(i)的最大值尽可能地小。
输出划分结果。
若有多解，则使前面的段尽可能地短。

二、解析

看到“最大值尽可能小”这种字眼，第一下就应该反应出可能要使用二分答案的方法了。
本题就是一个典型的二分答案。

即通过二分法枚举S(i)的最大值x，然后对于每一次枚举，判断是否可以保证分成k段后，每一段的和都不超过x，这是判断是容易的，可以在O(n)时间完成，然后二分的过程可以在O(logM)时间完成，M为和的最大可能值。这样总时间复杂度为O(nlgM)。

ps: 这题的输出有点坑，注意一下就行了，因为不是重点。

三、代码

#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
const int maxn = 500 + 5;
const LL INF = 5e9 + 5;
int kase, n, k, a[maxn];

bool isOK(LL max_sum) {
    int cnt = 0;
    LL sum = 0;
    for(int i = 0; i < n; i ++) {
        if(a[i] > max_sum) return 0;
        sum += a[i];
        if(sum > max_sum) cnt ++, sum = a[i];
        if(cnt > k) return 0;
    }
    if(sum) cnt ++;
    if(cnt > k) return 0;
    return 1;
}

void output(LL l) {
    vector<int> rev_ans;
    LL cur = 0;
    int cnt = 0;
    for(int i = n - 1; i >= 0; i --) {
        if(i + 1 == k - 1 - cnt) {  // 若剩下的数字量个剩下的分隔线数量相等
            cnt ++, rev_ans.push_back(-1);
            rev_ans.push_back(a[i]);
            continue;
        }
        cur += a[i];
        if(cur > l) cnt ++, rev_ans.push_back(-1), cur = a[i];  // -1代表分隔线
        rev_ans.push_back(a[i]);
    }
    for(int i = rev_ans.size() - 1; i >= 0; i --) {
        int ans = rev_ans[i];
        if(ans == -1) cout << "/";
        else cout << ans;
        cout << (i ? " " : "");
    }
    cout << endl;
}

int main() {
    cin >> kase;
    while(kase --) {
        cin >> n >> k;
        for(int i = 0; i < n; i ++) cin >> a[i];
        LL l = 0, r = INF;
        while(l < r) {
            LL mid = l + (r - l) / 2;
            if(isOK(mid)) r = mid;
            else l = mid + 1;
        }
        output(l);
    }
}

四、归纳

  • [最大值尽可能小]、[最小值尽可能大], 这类问题时，可以考虑二分答案。
  • 注意二分时判断OK后r等于多少，l等于多少不要搞错了。一般我们把范围想为[l, r]闭区间不容易错。所以不OK时 l=mid+1，因为不应该包含mid。此为，最好用l=1, r=2来验证一下是否会陷入死循环。