贪心
简介
贪心算法 ， 指得是每一次不考虑后面的状态 ， 在当前寻找一个最优的解法，从而得到最终的最优值。
但明显，这种算法只考虑当前而不考虑全局的思想，在有些题目中并不适用，所以 ， 当使用贪心思想的时候需要具有充分的证明可以判断此问题中贪心具有正确性。
适用范围
如果一个问题 ， 是可以拆成很多子问题的 ， 并且他们之间是相互独立的 ， 那么我们就可以通过贪心来不断得出子问题的最优解 ， 从而得出来此问题的最优解。
贪心模型及证明
入门小菜
题目描述
有 \(n\) 个人在一个水龙头前排队接水，假如每个人接水的时间为 \(T_i\)，请编程找出这 n 个人排队的一种顺序，使得 \(n\) 个人的平均等待时间最小。
解析
我们先想，每个人等待的平均时间最小 ， 那么就是让所有人的总等待时间最小 (最后除以个人数嘛) ， 那么我们可以转为求让所有人的等待时间最短。
然后我们考虑 ， 排在前面的人需要等待的时间， 后面的所有人也需要等，所以对于他接水的这段时间 ， 总需等待他和他之后所有人的人数乘本次的时间。
举个例子 ， 如果有 \(2\) 个人 ， 第一个人接水时间为 \(1s\) (带个单位) ， 第二个人接水时间为 \(2s\)。
如果排队的顺序为 \(1, 2\) 那么 \(1\) 接水的时候 \(1\) , \(2\) 都需要等待 \(1s\) ， 然后 \(2\) 接水需要等待 \(2s\) ， 总需要时间 \(4s\)。
如果排队的顺序为 \(2\), \(1\) 那么 \(2\) 接水的时候 \(1\), \(2\) 都需要等待 \(2s\)， 然后 \(1\) 接水需要等待 \(1s\) ， 总需要时间 \(5s\)。
明显 ， 把接水花费时间短的人排在前面 ， 总等待时间最小。
证明
设 \(T_i\) 表示第 \(i\) 个人的时间， \(i\) 后面还有 \(s\) 个人，为了让 \(T_i\) 放在 \(T_{i+1}\) 之前更优，就要满足 $$ T_i \times (s + 1) + T_{i + 1} \times s < T_{i+1} \times (s+1) + T_i \times s $$ 化简即得 \(T_i < T_{i + 1}\)，于是结果最优当且仅当 \(T\) 升序排列。
现在你就大概了解了贪心的含义及做法了 ， 下面我们来了解一些贪心的模型。
区间问题
Problem One
题目描述
从 \(n\) 个闭区间中选出尽量多的两两不相交的区间
Solution
把所有区间按照右端点排序 ， 不断选当前可选区间的右端点的最小值
证明
假设我们选出的方案是 \(a_1 , a_2 \cdots , a_m\)，考虑任意一个合法方案 \(b_1, b_2 \cdots b_m\)， 与我们找到的方案不同。 找到满足 \(a_1 = b_1 \cdots a_{i - 1} = b_{i - 1}\) 的 最大的 \(i\), 因为我们找到的 \(a_i\) 是满足条件的最小值， 那么肯定有 \(a_i \le b_i\)。
那么我们可以把 \(b_i\) 替换为 \(a_i\), 则 \(b\) 序列为 \(b_1, b_2 \cdots a_i\), \(b_i + 1 \cdots b_m\) 也是合法的。
因为对于情况 , 我们发现 替换为 \(a_i\) 不会变差, 那么 \(a\) 则为最优解。
Problem Two
题目描述
给定 \(n\) 个闭区间，在数轴上选尽量少的点，使每个区间中都有至少一个选中的点
solution
即上一问的区间数， 每次选择区间右端点即可
证明
如果存在一个区间，没有被所选的点覆盖 ， 那么他必定在上一问中被选出来作为新区间 ，矛盾 。
Problem Three
给 \(n\) 个闭区间染色，使得相交的区间颜色不同，求最少需要多少种颜色
solution
答案即为 第一问中每个区间相交的区间的个数的最大值 \(+ 1\)
Prolem Four
题目描述
从 \(n\) 个闭区间中选出尽量少的区间，使他们的并包含 \([1 , m]\)
solution
第一个区间选包含 \(1\) 的 右端点最大的区间 ， 然后把所有区间按照 左端点排序 ， 每次选择满足条件的右端点最大的区间，证明与Problem One 类似。
匹配问题
Problem One
题目描述
有 \(2N\) 张牌，上面的整数分别是 \(1 \sim 2N\)。你手上获得了其中的 \(N\) 张牌，你的对 手有另外 \(N\) 张。你和对手每次打出手中的一张牌，谁大谁赢，问最好情况下你能赢 多少次。
solution
因为你知道对方出的牌 (这不是作弊吗) ， 就能提前排布你的打法。
很容易想到运用田忌赛马的思想，设当前自己手里的牌为 \(i\) 。
如果对方的牌比 \(i\) 小 ， 那么直接拿下！
如果对方的牌比 \(i\) 大 ， 那么就用 \(i\) 去把对方的大牌顶掉。
Problem Two
题目描述
给出 \(2n\) 个元素，把他们配成 \(n\) 对 \((a_i , b_i)\)，使 \(\max(a_i + b_i)\) 最小。
solution
容易发现 ， \(a\) 的降序排列 配 \(b\) 的升序排列 ， 人话说 一个小数 配一个大数 ， 求最大值。
证明
\(a\) 按降序排列， \(b\) 按升序排列，设 \(1 \le i < j \le n\), \(1 \le k < l \le n\)。我们的匹配为 \(\max((a_i + b_k) , (a_j + b_l))\)。
交换后 , 对于 \(a_j + b_l\),\(a_i + b_k\), 可以得到 $$ \max\big((a_j + b_l), (a_i + b_k)\big) \le \max\big((a_i + b_k), (a_j + b_l)\big) $$
因为 \(a_i + b_k\) 是最大的,所以我们得到的序列肯定是更优的，证毕。
Problem Three
题目描述
给定两个长度为 \(n\) 的数组 \(a\), \(b\), 把他们配成 \(n\) 对 \((a_i , b_i)\) , 使 \(\sum^n_{i=1} a_ib_i\) 最大
solution
容易发现 ， 把 \(a\) ， \(b\) 从小到大排列 ， 逐位求积最优。
证明
与上题相似 ， 排列后设 \(1 \le i < j \le n\)，\(1 \le k < l \le n\)，我们的匹配为 \(a_i \times b_k + a_j \times b_l\)，交叉后得到 \(a_i \times b_l + a_j \times b_k\)，比较两者大小，用前式减去后式，得到 \((a_i - a_j \times (b_k - b_l)\)。
因为 \(a_i \le a_j\)，\(b_k \le b_l\)，故本式 \(\ge 0\)，可使我们匹配的序列更优。
Problem Four
题目描述
给定两个长度为 \(n\) 的数组 \(a\) , \(b\) , 把他们配成 \(n\) 对 \((a_i , b_i)\) , 使 \(\sum^n_{i = 1} |a_i - b_i|\)最小
solution
容易发现 ， 把 \(a\) ，\(b\) 从小到大排序 ， 逐位求差最优。
证明
设 \(1 \le i < j \le n\)，\(1 \le k < l \le n\)，我们的匹配为 \(|a_i - b_k| + |a_j - b_l|\)。 交叉后 , 得到 \(|a_i - b_l| + |a_j - b_k|\)，可以发现交叉后的值总比上面的值多 \(2(b_l - b_k)\), 则我们得到的匹配更优, 证毕。
邻项交换
Problem One
题目描述
\(n\) 个数对 \((L_i , R_i)\) , 定义 \(F_i=\lfloor \frac{\prod_{j = 1}^{i - 1} \times L_j} {R_i} \rfloor\), 求一个最小化 \(\max{F_i}\) 的排列。
solution
考虑相邻两个数对 ， 什么时候交换可以使答案变优。
设 \(T = \prod_{j = 1}^{i - 1} L_j\) , 第 \(i\) 个数对的 \(L\)，\(R\) 为\(l_1\)，\(r_1\)，第 \(i+1\) 个数对的\(L\)，\(R\) 为 \(l_2\) ，\(r_2\)。
交换前的值为 $$ F_i = \lfloor \frac{T}{r_1} \rfloor , F_{i + 1} = \lfloor \frac{T \times l_1}{r_2} \rfloor $$ 交换后的值为 $$ F_i = \lfloor \frac{T}{r_2} \rfloor , F_{i + 1} = \lfloor \frac{T \times l_2}{r_1} \rfloor $$ 我们设排序为 \(i\) ，\(i + 1\) 时答案更优 , 则可得 $$ \max(\lfloor \frac{T}{r_1} \rfloor, \lfloor \frac{T \times l_1}{r_2} \rfloor) > max(\lfloor \frac{T}{r_2} \rfloor, \lfloor \frac{T \times l_2}{r_1} \rfloor) $$ 因为 \(\lfloor \frac{T}{r_1} \rfloor < \lfloor \frac{T \times l_2}{r_1} \rfloor\)，并且 \(\lfloor \frac{T \times l_1}{r_2} \rfloor > \lfloor \frac{T}{r_2} \rfloor\)，故原式可以得到 \(\lfloor \frac{T \times l_1}{r_2} \rfloor > \lfloor \frac{T \times l_2}{r_1} \rfloor\)
化简得到 $$ T \times r_1 \times l_1 > T \times l_2 \times r_2 $$ 综上所述 , 按照 每个数的 \(l \times r\) 从大到小排列即可 ， 则证毕。
（更新中）
例题来源
P2970 [USACO09DEC] Selfish Grazing S
P6179 [USACO15DEC] High Card Wins S