二分答案——通过答 案反推,验证合法性从而确定最优解
给出一个长度为 N 的正整数数列,现在要把它分成 K 段,且每一段里所有数字的和都不超过T,问T的最小值是多少?
例:2354332,分成3段
T最小的分段:[23] [54] [332],T=9(5+4)
阶段:当前分割到第几段
决策:在哪个位置分割
怎么确定最优子结构?
如果一直选取最优,每段尽可能小,会导致分到最后剩下的太多~!
这样也不是最优~
所以最优化策略还是不行
此题看起来很接近划分问题?
构造法的条件:可以通过计算或者总结得出规律
但这道题没什么规律..
已知 T,很容易验证数列是否能被分为M段,且每段和都不超过 T
如果数列中有个很大的数,则我们的初始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;
}
1.确定解的范围,也就是进行二分的上下边界
2.对这个解的范围进行二分查找,每一轮二分,对于当前的中值利用贪心进行验证,如果验证通过则说明解的范围需要缩小,否则需要扩大
3.当二分结束,确定了最小/最大的通过验证的解,就是最终答案
题目所求的最优解,往往是某种上下界,比如数列划分为M段后每段的和的最大值T,就是一种上界
如果给定了一个值,可以很容易地用贪心法验证这个值是不是一个可行解
这个值和某个用来验证合法性的条件,一定存在某种单调性关系
将题目修改为:每段都至少包含一个数字 T,求 T的最大值
如果此时M=2,二分会先验证T=2再验证T=1,最后得到T最大是1,但实际上T最大是4