T1 数列分段 Section II

传送门：洛谷P1182

题意：

把 \(n\) 个数分成 \(m\) 段，使 \(m\) 段和的最大值最小，求这个值；

题解：

因为题目要求最大值的最小值，很明显的一道二分答案的板子题，我们二分这个最大值，
因为是区间和，我们用前缀和来维护，二分区间就是 [ \(sum[1]\) , \(sum[n]\) ] ：

    for (int i = 1; i <= n; ++ i) {
        scanf("%d", &a[i]);
        sum[i] = a[i] + sum[i - 1];
    }
    Max = sum[n], Min = sum[1];
    ll l = Min, r = Max;
    while (l < r) {
        ll mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }

对于CHECK函数：

因为 \(m <= n\) ,数据保证能分成 \(m\) 段，我们枚举 \(1\) ~ \(n\) , 判断是否有小于等于 \(m\) 个区间的最大值小于等于 \(mid\) , 如果是，那就向 \(l\) ~ \(mid\) 里二分，如果非，那就二分 \(mid + 1\) ~ \(r\);

int check(ll x) {
    int cnt = m, l = 0, r = 1;
    while (cnt --) {
        while (sum[r] - sum[l] <= x && r <= n) ++ r;
        l = -- r;
        if (l == n) return 1;
    }
    return 0;
}

贴代码：

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

const int maxn = 1e5 + 5;
ll sum[maxn], Max, Min;
int n, m, a[maxn];

int check(ll x) {
    int cnt = m, l = 0, r = 1;
    while (cnt --) {
        while (sum[r] - sum[l] <= x && r <= n) ++ r;
        l = -- r;
        if (l == n) return 1;
    }
    return 0;
}

void read() {
    scanf("%d%d", &n, &m);
    Min = 0x3f3f3f3f;
    for (int i = 1; i <= n; ++ i) {
        scanf("%d", &a[i]);
        sum[i] = a[i] + sum[i - 1];
    }
    Max = sum[n], Min = sum[1];
    ll l = Min, r = Max;
    while (l < r) {
        ll mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    printf("%lld\n", l);
}

int main() {
    read();
    return 0;
}