贪心贪心的反悔

贪心时常作为一个贬义词出现。但是在做题的时候，我们还是不可避免的需要使用贪心算法

一、什么是贪心算法

贪心的基本思想是通过局部选择最优来达成全局最优，说人话就是在每一步决策中，只选择当前状态下 “看起来最好” 的选项（局部最优），不回头考虑过去的选择，也不预判未来的整体情况。最终，通过一系列局部最优选择的累积，得到问题的全局最优解。

不过到这里，也许你会有像我一样的疑惑。这不就是证明格局小了嘛！还最优，优个.....。不过既然作为一种算法，它自然是有它的道理的。下面，我们来举几个例子

想象一下你在菜市场买完菜，你拿了一张一堆零钱，一共94块，你想要自己手上的钱尽可能地少，你该怎么办？很显然，你需要找尽可能大的面值的钱，来对自己的前进行找0，这就是贪心的雏形。

二、什么情况能用贪心？

1.最优子结构

说人话就是一个大问题的最优解，是由它拆分成的小问题的最优解组合起来的。就像刚刚的找0，最后你拿的钱的张数最小时，你每一次找0获得的钱的张数也是最少。

2.不纠结 “过去的选择”

前面的选择并不影响我做后面的选择，比如背包问题，前面放进去的东西占用了背包的体积，影响后面我选择放什么东西，并且每个物品价值又不一样，肯定影响我的最大价值的计算。所以背包问题不能用贪心，而是动态规划。

总结：

当问题的每一步局部最优选择，都不会让后面的选择 “更差”，且最终能拼出全局最优时，贪心就是对的。

例题

洛谷：P1803 凌乱的yyy / 线段覆盖 - 洛谷

先看满不满足贪心的基本条件：

1.最优子结构 当然满足，最终他想参加尽可能多的比赛，那么每一次选择他都得选持续时间最短的来保证数量

2.不影响后续选择 其实你可能会问说是上一个比赛实际上也是影响下一个比赛的选择的。因为他不能同时搞两个比赛，这和背包问题十分相似，由此你可能会得出结论：dp。但是区别是背包问题中不同的物品价值也不一样，但这个问题里，题目只要求数量，也就是说我们可以看作每个比赛之间实际上对于yyy来说没有区别。凭借这一点不同，我们就可以确定用贪心

附上AC代码
 

#include<bits/stdc++.h>
using namespace std;
struct Com {int start;int end;
}c[1000100];
int cmp(Com a, Com b){return a.end<b.end;
}
int main(){int n;cin>>n;for (int i=0;i<n;i++){cin>>c[i].start>>c[i].end;}sort(c,c+n,cmp);int pre=c[0].end;int cnt=1;for(int i=1;i<n;i++){if(c[i].start >= pre){cnt++;pre=c[i].end;}}cout<<cnt<<"\n";return 0;
}

三、反悔

当然，贪心也有出错的时候，比如你要选 3 门课，目标是总学分最高，且课程时间不冲突。

• 普通贪心可能会先选 “当前能看到的学分最高的课”，但选完后发现，剩下的时间只能选两门低学分课，总学分反而不如 “放弃第一门高学分，选另外三门中等学分” 的组合。
• 这时候，“反悔” 就是：先选了第一门课，后来发现有更好的组合，就把第一门课 “退掉”，换成更合适的 —— 通过修正之前的选择，达到更优的结果。

例题

这一点不好论述，我们举一个例子来看   P3620 [APIO/CTSC2007] 数据备份 - 洛谷​​​​​​​

盖云给楼两两配对 使得距离之和最小。

还是先来看满不满足贪心的两大原则：

1.最优子结构

如果咱们选的 K 个距离是最优解（总和最小），那么随便挑出其中一个距离 d，剩下的 K-1 个距离也一定是 “去掉 d 以及它旁边两个距离后” 能选出的最优解。

为啥呢？假设剩下的 K-1 个不是最优的，那肯定有更优的选法。那咱们把原来的 K-1 个换成这个更优的，再加上刚才挑出的 d，总距离就会更小 —— 这就和 “原来的 K 个是最优解” 矛盾了。

所以问题符合 “最优子结构”：大问题的最优解里，藏着小问题的最优解。

如果你看得晕头转向，请看以下的例子

假设现在有一串糖葫芦，山楂编号是 1、2、3、4、5、6、7（相邻的挨在一起）。
你要挑 3 颗（K=3），不能挨在一起，总重量最小。
你最后挑的是 1、3、6（最优解），总重量是最小的。

现在看其中一颗，比如 3。
当你把 3 从糖葫芦里拿走时，按照规则，它左边的 2 和右边的 4 也不能再用了（因为如果用了 2 或 4，就会和 3 挨在一起，相当于办公楼重复用了）。
所以剩下能选的山楂只有 1、5、6、7 了（去掉了 3，以及它旁边的 2、4）。

现在问题来了：你之前选的另外两颗是 1 和 6，这两颗正好在剩下的 1、5、6、7 里面，而且它们不挨在一起。
这两颗 1 和 6，是不是从 1、5、6、7 里挑 2 颗（K-1=2）的最优解？当然是啊，不然为什么不选5和7，既然是，那就证明全局最优解包括了局部最优

2.贪心性选择

每次从能选的距离里挑最小的，选完后排除它左右的（避免冲突），重复 K 次。由此可见，我们在每一次选局部最优的时候能保证最后的全局最优。这就是贪心性质的体现。

上代码和注释

#include<bits/stdc++.h>
using namespace std;int read(){int s=0,fl=1;char w=getchar();while(w>'9'||w<'0'){if(w=='-')fl=-1;w=getchar();}while(w<='9'&&w>='0'){s=s*10+(w^48);w=getchar();}return fl*s;
}// 存储相邻办公楼距离的结构体
struct Place {int val;  // 当前位置的距离值（d_i = s[i+1]-s[i]）int l;    // 左邻居的索引（双向链表左指针）int r;    // 右邻居的索引（双向链表右指针）
} p[100010];  // 最多有1e5-1个相邻距离// 优先队列（最小堆）中的元素结构
struct Node {int val;  // 距离值int id;   // 该距离在Place数组中的索引// 重载小于号，使优先队列成为最小堆（默认是最大堆）bool operator < (const Node &it) const {return val > it.val;  // 小值优先出队}
};int n, m, ans, last;  // n:办公楼数量；m:K值；ans:总距离和；last:上一个办公楼的位置
bool vis[100010];     // 标记距离是否被排除（不可选）// 删除操作：将当前距离的左右邻居从链表中移除（因为选了当前距离后，左右邻居不能再选）
void Delete(int x) {// 更新当前节点的左右指针，指向左右邻居的邻居p[x].l = p[p[x].l].l;p[x].r = p[p[x].r].r;// 更新左右邻居的邻居的指针，指向当前节点（跳过被删除的节点）p[p[x].l].r = x;p[p[x].r].l = x;
}priority_queue<Node> q;  // 最小堆，用于快速获取当前最小的可用距离int main(){n=read();m=read();last=read();  // 第一个办公楼的位置// 计算相邻办公楼的距离，并初始化双向链表for (int i = 1; i < n; ++i) {int in;in=read();  // 第i+1个办公楼的位置p[i].val = in - last;  // 计算距离d_i = s[i+1]-s[i]last = in;p[i].l = i - 1;  // 左邻居是i-1p[i].r = i + 1;  // 右邻居是i+1q.push((Node){p[i].val, i});  // 加入最小堆}// 边界处理：第0个和第n个位置设为极大值（避免越界访问）p[0].val = p[n].val = 2e9;// 选择m个不相邻的距离for(int i=1;i<=m;i++){// 弹出堆中已被排除的距离（vis为true的）while (vis[q.top().id]) q.pop();Node now = q.top();  // 当前最小的可用距离q.pop();ans += now.val;  // 累加总距离// 标记当前距离的左右邻居为已排除（不可选）vis[p[now.id].l] = vis[p[now.id].r] = true;// 合并操作：将当前距离替换为“左右邻居距离之和 - 当前距离”// 这是为了应对“反悔”情况（如果后续发现选左右邻居更优）p[now.id].val = p[p[now.id].l].val + p[p[now.id].r].val - p[now.id].val;q.push((Node){p[now.id].val, now.id});  // 将合并后的值重新加入堆// 删除左右邻居（从双向链表中移除）Delete(now.id);}cout << ans;  // 输出最小总距离return 0;
}

 如何反悔的呢？

// 计算“反悔值”：用左右邻居的和减去当前值
p[now.id].val = p[p[now.id].l].val + p[p[now.id].r].val - p[now.id].val;
// 将“反悔值”重新加入堆，留待后续选择
q.push((Node){p[now.id].val, now.id});

1. 反悔值：left + right - current 的本质是 “如果后悔选了 current，转而选 left 和 right，需要补充的差值”。当这个反悔值被选中时，总和会自动修正为 left + right，实现 “纠错”

那是如何判断需不需要反悔的呢？

反悔的触发是自动的

当 “反悔值” 比当前堆中其他可用节点更小时，贪心算法会自然选择它，从而实现 “反悔”。例如：
第一次选了 d2=1 后，加入了反悔值 3（2+2-1）。此时堆中剩下的可用节点是 3（反悔值）和 9（d4），由于 3 更小，第二次选择会自动选 3，相当于 “撤销选 d2，改选 d1 和 d3”。

如果反悔值不优（比如 d_left + d_right 比 d 大），那么反悔值会较大，后续选择不会选它，相当于 “不反悔”，之前的选择保持有效。