贪心

· · 算法·理论

贪心策略是一种可以比较快求解的方法，它一般配着排序使用，贪心是以局部最优解顶替全局最优解，通常贪心需要证明。 —— MoonCake2011 2.5 years ago as Libingyue2011

贪心的核心：每一步都做“当前看起来最划算/最优”的选择，并希望这些局部最优选择最终拼出全局最优解。

它常见于竞赛里，优点是：思路清晰、实现简单、复杂度低。难点是：不是所有题都能贪心，关键在于证明。

1. 贪心算法的一般套路

  1. 定义“每一步怎么选”（选择规则 / 排序规则）
  2. 证明这个规则不会把最优解弄丢
  3. 实现（通常：排序 + 扫描 / 优先队列）

很多贪心都长这样：

2. 贪心什么时候“可能正确”

一个直觉判断：

这就引出两种常用证明方式。

3. 两种最常用的证明方法（新手必会）

3.1 反证法 / 交换法

思路：假设有个最优解 S 没按你的贪心选。 证明：你可以把 S 的某一部分“换成”你的贪心选择，不变差，于是存在一个同样最优的解以贪心选择开头。

3.2 归纳 / 最优子结构

证明第一步贪心选完后，剩下的子问题仍然是同类问题，并且你的选择让子问题“最好做/不更差”。 于是：最优解 = 当前贪心一步 + 子问题最优解。

题目

给 n 个活动，每个活动是一个区间 [l_i, r_i]。选出最多活动，使得它们互不重叠。

贪心策略

按结束时间 r 从小到大排序，每次选择当前能选的、结束最早的活动。

为什么对（交换论证直觉）

如果最优解里第一个选的活动结束得更晚，那么把它换成“结束更早”的活动，不会减少后面能选的数量（反而更可能留出空间）。

实现要点

维护上一个选中活动的结束时间，扫描即可。

题目

给很多区间 [l_i, r_i]，目标覆盖 [L, R]（每个点都在某个选中的区间里）。求最少选多少区间。

贪心策略（非常经典）

为什么对（直觉）

你在某一步必须选一个能接上 pos 的区间，那当然希望它把右端点推得最远，这样后面需要的区间数不会更多。

题目

给 n 个区间，选择尽量少的点，使得每个区间至少包含一个选中的点。

贪心策略

按右端点 r 升序排序： 遇到一个还没被点覆盖的区间，就在它的右端点 r 放一个点。

为什么对

把点放得越靠右，越可能覆盖后面的区间；对当前区间来说，放在 r 一定合法且“最不浪费”。

题目

部分背包。

背包容量为 W，物品 i 有重量 w_i、价值 v_i，可以拿走一个物品的一部分。最大化总价值。

贪心策略

按单位价值 \dfrac{v_i}{w_i} 从大到小排序，能装多少装多少，最后一个可以装一部分。

为什么对（反证法）

如果你拿了单位价值低的部分，却没拿单位价值高的部分，把它们交换会让价值变大，不可能是最优。

代码 code by MoonCake2011 2.5 years ago as Libingyue2011：

#include<bits/stdc++.h>
using namespace std;
struct coin{
    int m,v;
}a[110];
bool operator < (coin x,coin y){
    return x.v*y.m<y.v*x.m;
} 
bool operator > (coin x,coin y){
    return x.v*y.m>y.v*x.m;
} 
void quicksort(int l,int r){
    int i=l,j=r;
    coin flag=a[l+r>>1];
    do{
        while(a[i]>flag) i++;
        while(a[j]<flag) j--;
        if(i<=j) swap(a[i++],a[j--]);
    }while(i<=j);
    if(l<j) quicksort(l,j);
    if(i<r) quicksort(i,r);
}
int n;
int t,l;
double ans;
int main() {
    cin>>n>>t;
    for(int i=1;i<=n;i++)
        cin>>a[i].m>>a[i].v;
    quicksort(1,n);
    for(int i=1;i<=n;i++)
        if(l+a[i].m<t)
            ans+=a[i].v,l+=a[i].m;
        else{
            ans+=(t-l)*1.0/a[i].m*a[i].v;//装剩余空间
            break;
        }
    printf("%.2lf",ans);
   return 0;
}

哈夫曼编码

题目

荷马史诗。

给字符频率，构造前缀编码，使总编码长度最小。

贪心策略

每次取频率最小的 k 个节点合并（用小根堆反复合并）。

为什么对（直觉）

频率最低的字符对总长度贡献最小，把它们放在更深处（更长编码）损失也最小；合并就是把“更深一层”的代价累加起来。

问题

但这样会出现一些问题，因为这样做会导致最后一次合并的可能不是 k 个，可以将深处的节点放到根的儿子更优。

解决方案

加入一些出现次数为 0 的字符，补到 k-1 的倍数个即可避免问题。

5. 做贪心题的一些方法

当然，你可以猜结论。

例题：P1080。

假设只有两个大臣，为 1 号与 2 号。

手上两个数分别是 (a_1,a_1)，(a_2,b_2)，国王手上两数是 (a_0,b_0)。

假设 把 1 号排 2 号前面最优，1 号排 2 号前面的答案为 \max(\dfrac{a_0\times a_1}{b_2},\dfrac{a_0}{b_1})。

2 号排 1 号前面的答案为 \max(\dfrac{a_0\times a_2}{b_1},\dfrac{a_0}{b_2})。

列出不等式 \max(\dfrac{a_0\times a_1}{b_2},\dfrac{a_0}{b_1})<\max(\dfrac{a_0\times a_2}{b_1},\dfrac{a_0}{b_2})

同除 a_0 得出 \max(\dfrac{a_1}{b_2},\dfrac{1}{b_1})<\max(\dfrac{a_2}{b_1},\dfrac{1}{b_2})。

显然 \dfrac{a_1}{b_2}\ge \dfrac{1}{b_2}，\dfrac{1}{b_1}<\dfrac{a_2}{b_1}，所以只用考虑 \dfrac{a_1}{b_2} 与 \dfrac{a_2}{b_1} 的大小关系。

那么就是 \dfrac{a_1}{b_2}<\dfrac{a_2}{b_1}。

因为 0<b_1,b_2，所以需要满足 a_1\times b_1 < a_2\times b_2

所以按 a\times b 排序就可达最优解。

再看数据范围，1 \le n\le 1,000,0 < a,b < 10000，答案超了 10^{30000}，需要用高精度。

这种证明方法就是交换法。

duel。

从大往小枚举，最优策略绝对是能攻击就攻击。

直接模拟即可。

为何，如果一个怪兽不被先枚举到的怪兽 A 攻击，那

sa。

发现每个车的超速的时间是一个区间，于是求出后跑经典的区间覆盖就行了。

S。

首先，一段出现 k 的区间可以不用考虑，我们也不用去考虑改变 k。

那我们用 k 给序列划分成很多段，这些段里都没有 k。

对于每个段单独考虑，从左往右扫，如果遇到一个一个前缀出现了 [1,k-1] 的所有数，那我们将那个前缀最后一个数改为 k，之所以是最后一个数，根据贪心它能往后影响更大。

P。

对于一个子序列 s，已知它在串里 p_1,\dots,p_k 位置均可以成为结尾，那么我们发现位置最靠前的一定选择范围更广，只用保留最靠前的那个就行了。

于是有个暴力就是每个询问依次向后扫，直接判断就行了。

从 s_{i-1} 加入一个字符 s_i 时，我们需要快速找到下一个 s_i 的位置。

此时可以将每个数对应的位置存下来，二分查找就行了。

fish。

我的做法：

先对每个可以随意交换的连续段处理出来，并把每个连续段的 0/1 的个数求出来。

从前往后枚举，对于一个两个都不能修改的位置，直接不修改跳过就行了。

对于一个位置，如果只有其中一个不能修改，那我们考虑用哪个可修改的所在的连续段的 0/1 尝试匹配（这就是为什么要求出连续段的 0/1 个数，因为那里的 0/1 可以随便移动）。

记得没配上桶里也要减减。

这一步为何最优：因为每一个 0/1 最多产生一个贡献，迟早要产生贡献还不如先产生贡献了。

接着对于两边都可以随意移动的，随便匹配一个 0/1 就行，其实匹配 0/1 都没关系的，还是上面那个结论。

记得没配上桶里也要减减。

然后就做完了。

This。

直接复制我的题解。

注意：此文中下标从 1 开始。

首先，一看数据范围，再看计算方式。

就知道可能会爆 long long。

上 __int128。

第二，因为会拼接无限个 a 序列，所以必须让 a 序列的和非负，不然越减越小。

第三，既然都非负了，所以第三个操作就没用了。

设 a 向后拼接一个 a 数列的数列叫 c。

证第三个只用证 c 的和非负时，一定存在存在自然数 1\le k_0 \le n，使得对于所有 k_0\le k \le 2\times n，都满足 c 中下标在区间 [k_0,k] 内的所有数的和非负。

其实 k_0 就是满足 c 中 \sum_{i=1}^{k_0-1} c_i 最小的数。

因为 \sum_{i=1}^n c_i \ge 0，所以当 k_0 > n 时，答案没有 k_0-n 优，所以可以取到使 1\le k_0\le n 满足的 k_0。

对于每个 k，\sum_{i=k_0}^k c_i=\sum_{i=1}^k c_i-\sum_{i=1}^{k_0-1} c_i。

又因为 \sum_{i=1}^{k_0-1} c_i \le \sum_{i=1}^k c_i，这是因为 \sum_{i=1}^{k_0-1} c_i 最小。

所以 \sum_{i=1}^k c_i-\sum_{i=1}^{k_0-1} c_i \ge 0。

故成立。

那么现在只考虑前两个操作。

现在我们是对整体进行考虑，那么顺序就没用喽。

从小到大排个序。

因为你删数一定先删较小数。

这样更能让序列加的数更多，序列和更容易非负。

排序后，枚举需要做几次 2 操作。

根据上面的讨论。

做 i 次 2 操作一定是做的 1,2,\dots,i 的数。

剩余的用前缀和计算是否非负。

注意：你可以做 0 次 2 操作。

计算答案很简单吧。

就做完了。

注意不能将数列删空。

好玩的。

将与 1 和 n 不连通的点删掉。

先找出任意一棵生成树。

对于图中的所有的环，我们发现，对于只有一条非树边单独构成的环塞进线性基里异或可以覆盖所有的情况。

因为两个相交的环异或起来就可以成为一个大环。

又因为可以重复走，所以环可以随便走。

找到生成树上 1 到 n 的路径，将一条非树边单独构成的环塞进线性基里查询就行了。

膜拜 meng0740。

发现数据随机，开始骗分。

有一个伪的贪心就是按 \dfrac{a}{b} 排序，枚举断点找最大值。

因为数据随机，这个断点可以枚举中点附近的 100 左右就可以了。

然后每次在断点附近的 10 个点用 dfs 搜一下就能过了。

Problwm。

一个贪心，我们尽量让性价比最高的物体选的越多越好，但是这是错的。

但是这样可能会出现缝隙填不满背包导致不优，所以可以尝试先选择性价比最高的物体 k，再考虑其他的。

解决这种背包的解法一般是同于最短路，于是考虑以物品 k 为模数进行同余最短路的图论建模。

设 f_i 为 i\equiv V \pmod v_k 最大的 C-\lfloor \dfrac{V}{v_k}\rfloor\times c_k。

接下来我们可以用转圈来做了。

This is a waterest problem。

先将每个区间的价值转化为前缀和形式。

先考虑 k=1 的情况，对于每个位置 l 为起点，寻找 [l+L-1,l+R-1] 区间的前缀和的最小值，这用 st 表就能做到。

接着我们要求，每次查询都用时比较短。

那我们尝试将所有起点的答案建个结构放入堆里，排序，每次取堆顶，删决策。

假设 [l+L-1,l+R-1] 中间断掉了一个点 k，那我们可以将这个区间答案裂为 2 个区间的答案。

于是我们可以在结构体里中套一个堆进行这个区间答案的维护。

每次删点的时候相当于将一个子区间的答案删掉，加入两个新的子区间，用堆很好做主要是因为我们要删除的那个绝对是堆顶。

记得在 st 表里维护位置。

这样算算复杂度，就是 O(n\log n) 的。

当然还有一个更加优秀的实现方式，就是不用在结构体里维护堆，直接在结构体里维护管辖区间。

每次删决策是直接在大堆里删堆顶，加入两个子区间。

做完了，个人认为评不到紫。

本文章梳理知识点部分的框架由 AI 辅助生成，保证人的贡献远大于 AI。