AKSZ - 第3/4课笔记
2024-06-09 17:35:53
发布于：广东
21阅读
0回复
0点赞
贪心算法
通过每一步都作出局部最优的选择，得到（也有可能得不到）全局最优解。贪心的题目通常和dp的很相似，当不确定能不能使用贪心时可以写多个贪心方案并取max/min骗分。
一些贪心的证明推导思路
- 无奈法：讨论哪些损失是无法避免的
- 局部法：怎样推导出下一个局部最优解
- 交换法：当从多个方案中找最优的时，把最大和第二大交换一下是否更优
- 反证法：手搓数据推翻怀疑错误的贪心
反悔贪心 (难点)
在新的条件出现使得之前的选择不再是最优时，反悔之前的选择
通常实现方法是通过priority_queue储存之前的选择，如果有更优的就pop掉最劣的并push进新的选择
二分算法
对于一个单调的序列，可以通过二分在O(logn)内找到元素的位置
algorithm中有两个函数，upper_bound以及lower_bound
他们分别有三个参数，搜索的起始位置，中止位置，目标。
upper_bound的功能是在一个 升序序列 中找到第一个 >目标的地址
lower_bound则是找到第一个 >= 目标的地址
使用它们可以减少代码量
二分模板：
int l, r, mid, ans;
while (l<=r){
mid=l+r>>1;
if (check(mid)){
ans=mid;
//.....
} else {
//.....
}
}
小数二分模板：
double eps=1e-6; //精度
double l, r, mid;
while (r-l<=eps){
mid=(l+r)/2;
if (check(mid)){
//.....
} else {
//.....
}
}
有帮助，赞一个