算法与数据结构高手养成:朴素的贪心法(下)二分答案
Srlua小谢 2024-06-30 11:05:17 阅读 59
✨✨ 欢迎大家来访Srlua的博文(づ ̄3 ̄)づ╭❤~✨✨
🌟🌟 欢迎各位亲爱的读者,感谢你们抽出宝贵的时间来阅读我的文章。
我是Srlua小谢,在这里我会分享我的知识和经验。🎥
希望在这里,我们能一起探索IT世界的奥妙,提升我们的技能。🔮
记得先点赞👍后阅读哦~ 👏👏
📘📚 所属专栏:算法与数据结构高手养成
欢迎访问我的主页:Srlua小谢 获取更多信息和资源。✨✨🌙🌙
目录
算法与数据结构高手养成:朴素的贪心法(下)二分答案
例:数列分段
思路1:最优化策略
思路2:构造法
思路3:逆向思考
思路3的局限性
用二分法降低验证次数
用二分法降低验证次数:例
代码:数列分段
二分答案法的一般步骒
适用二分答案法的问题特性
不符合单调性的例子
算法与数据结构高手养成:朴素的贪心法(下)二分答案
二分答案——通过答 案反推,验证合法性从而确定最优解
例:数列分段
给出一个长度为 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;
}
二分答案法的一般步骒
1.确定解的范围,也就是进行二分的上下边界
2.对这个解的范围进行二分查找,每一轮二分,对于当前的中值利用贪心进行验证,如果验证通过则说明解的范围需要缩小,否则需要扩大
3.当二分结束,确定了最小/最大的通过验证的解,就是最终答案
适用二分答案法的问题特性
题目所求的最优解,往往是某种上下界,比如数列划分为M段后每段的和的最大值T,就是一种上界
如果给定了一个值,可以很容易地用贪心法验证这个值是不是一个可行解
这个值和某个用来验证合法性的条件,一定存在某种单调性关系
不符合单调性的例子
将题目修改为:每段都至少包含一个数字 T,求 T的最大值
如果此时M=2,二分会先验证T=2再验证T=1,最后得到T最大是1,但实际上T最大是4
希望对你有帮助!加油!
若您认为本文内容有益,请不吝赐予赞同并订阅,以便持续接收有价值的信息。衷心感谢您的关注和支持!
声明
本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。