数列分段 II

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 973 字

二分段和上限，贪心判定段数是否够用

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1436
// 题意：把长度为 N 的非负整数数列分成 M 段连续子段，求「每段和的最大值」的最小可能值。
// 思路：二分答案 + 贪心判定。
// 1. 二分每段和的上限 x，从左到右贪心装段，装不下就新开一段。
// 2. 所需段数不超过 M 说明 x 可行，可以继续调小。
// 复杂度：O(N log(sum)) 时间 / O(N) 空间
// 易错点：二分下界应为数列最大元素（单段和不可能小于它），不是 0，否则判定逻辑没问题但初始区间太大。
// 易错点：单个元素可能大于 x，此时无论怎么分都不行，判定里要用「新开一段后仍超限」来识别。
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    if(!(cin >> n >> m)) return 0;
    vector<long long> a(n);
    long long l = 0, r = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        l = max(l, a[i]);
        r += a[i];
    }
    while(l < r){
        long long mid = (l + r) / 2;
        int cnt = 1;
        long long sum = 0;
        for(int i = 0; i < n; i++){
            if(sum + a[i] > mid){
                cnt++;
                sum = a[i];
            }else{
                sum += a[i];
            }
        }
        if(cnt <= m) r = mid;
        else l = mid + 1;
    }
    cout << l << "\n";
    return 0;
}

数列分段 II

正文

一本通·提高篇的其它内容