算法与数据结构高手养成：朴素的贪心法(下)二分答案

Srlua

发布于 2024-06-07 16:15:39

740

发布于 2024-06-07 16:15:39

文章被收录于专栏：CSDN社区搬运CSDN社区搬运

算法与数据结构高手养成:朴素的贪心法(下)二分答案

二分答案——通过答案反推，验证合法性从而确定最优解

例:数列分段

给出一个长度为 N 的正整数数列，现在要把它分成 K 段，且每一段里所有数字的和都不超过T，问T的最小值是多少?

例:2354332，分成3段

T最小的分段:[23] [54] [332]，T=9(5+4)

思路1:最优化策略

阶段:当前分割到第几段

决策:在哪个位置分割

怎么确定最优子结构?

最优 =最大/最小?

如果一直选取最优，每段尽可能小，会导致分到最后剩下的太多~！

最优=最接近某个值(比如“数字和:段数”)?

这样也不是最优~

所以最优化策略还是不行

思路2:构造法

此题看起来很接近划分问题?

构造法的条件:可以通过计算或者总结得出规律

但这道题没什么规律..

思路3:逆向思考

已知 T，很容易验证数列是否能被分为M段，且每段和都不超过 T

设置一个足够小的 T 作为起始值，T 可以是理想情况的下界
验证对于当前的T是否可以满足条件(分成M段，每段和小于等于 T)
若不满足则T=T+1，直到找到最小的满足条件的 T

思路3的局限性

如果数列中有个很大的数，则我们的初始T就需要一直加，需要做很多重复工作~

此时我们可以使用二分法

用二分法降低验证次数

给答案规定一个上下界，作为二分起始区间。本题中，T的下界是(数列和÷段数)，上界是所有数字的和

对当前区间求中值mid，并用贪心法进行验证

如果每段和都不超过mid时，可以划分为不多于M段，则答案在左半区间;如果划分的段数大于M，或者有数字大于mid导致不能完成划分，则答案在右半区间

用二分法降低验证次数:例

发现18取大了，所以往左半区间继续求mid值

此时，说明最优解在9-13之间

此时发现它最少只能分四段了，说明最优解是11

代码:数列分段

#include<bits/stdc++.h>
using namespace std;

int n, m;
int a[100001];

int segmentation(int ub) {
    int count = 0, res = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > ub)
            return INT_MAX;
        if (count + a[i] <= ub)
            count += a[i];
        else {
            count = a[i];
            res += 1;
            if (res > m)
                break;
        }
    }
    return res + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    
    int l = sum / n, r = 1000000000;
    if (sum < r)
        r = sum;
    while (l < r) {
        int t = (l + r) / 2;
        if (segmentation(t) <= m)
            r = t;
        else
            l = t + 1;
    }

    cout << l << endl;
    return 0;
}