Pre

1. 某些题思维量很大，但其中很大一部分是在找性质或者其他一些什么地方上，属于贪心的部分并不多，分类时按照其贪心思维部分分类。
2. 以下，按照贪心正确性证明方式对常见贪心策略进行分类总结并附例题
3. 某些题容易想到多种证明方式，不重复列出

无需考虑后向影响的局部最优等于全局最优

优先进行的决策的贡献总大于其后进行的所有决策的贡献，即局部决策时无需考虑后向影响（如局部决策不同导致的代价差异进一步导致后向决策无法选择贡献更大的选项）

• 给定一个字符串 S 和一个可重字符集合 T，你可以操作若干次，每次拿出 T 中的一个字符去消除 S 中的一个字符，覆盖后 T 中这个字符消失，怎样才能使 S 的字典序最大。
• 给定一个 l ⩽ $10^5$ 位的正整数 n ，去掉其中的任意 k 个数字，并把剩下的数字按原来的顺序形成一个新的非负整数，求可以得到的最大的整数。link

后向影响最小的局部最优等于全局最优

即决策方案同时满足对后向决策的负面影响最小和当前局部决策贡献最优

• 把长度为 N ⩽ $2*10^5$ 的字符串分成尽量多的段，使任意相邻两段不同。link
• 有 3N 个数，你需要将他们分成 N 组，每组恰好三个数，权值为这三个数的中位数，最大化这 N 个组的权值和。link
• 给定 n 个闭区间，在数轴上选尽量少的点，使每个区间中都有至少一个选中的点。
• 给定 n 个区间，选出尽可能多的区间，保证数轴上的任意一点最多被覆盖两次。link
• 是否存在一个 n 排列 p，∀i, pi ∈ [$l_i,r_i$]。link(经过简化)
• 有 2N 张牌，上面的整数分别是 1 ∼ 2N。你手上获得了其中的 N 张牌，你的对手有另外 N 张。你和对手每次打出手中的一张牌，谁大谁赢，问最好情况下你能赢多少次。link

证明不优/不劣

有贪心策略，只需证明任意方案向策略方案调整都得到不劣答案、策略方案向任意方案调整都得到不优答案即可。这两种方法本质相同，但某些时候其中一种比另一种更好证明

• 从 n 个闭区间中选出尽量多两两不相交的区间。link
• 给 n 个闭区间染色，使得相交的区间颜色不同，求最少需要多少种颜色。
• 从 n 个闭区间中选出尽量少的区间，使他们的并包含 [1, m]
• 有 N 件物品，每件物品有质量 Mi 和价值 Vi，还有 K 个袋子，第 i 个袋子可 容纳的最大质量为 Ci，每个袋子只能装一件物品，可以获得的最大价值是多少？link

Exchange Arguments

严格来说，元素交换策略本质还是证明不优、不劣，但是思维方式上与证明不优、不劣的其他题有较大差距，且大多有显著特征且与序列强关联，遂单独列出。 选择序列中相邻（或任意）元素（或元素组合），考虑什么条件下交换元素位置可以得到更好的答案，通常是列柿子+推柿子最终得到策略（使用元素交换策略的题目中，元素间必须满足偏序关系，即自反性，反对称性和传递性）

• 给出 2n 个元素，把他们配成 n 对 (ai, bi)，使 max(ai + bi) 最小。link
• 给定两个长度为 n 的数组 a, b，你可以将 a 中的元素打乱，使得 $\sum_{i=1}^{n} a_ib_i$ 最大
• n 个人按顺序接水，第 i 个人接水的时间为 Ti，问如何排队可以使所有人的平均等待时间最小。
• 给两个长为 n 的数组 a, b，可以将 a 中的元素打乱，使 $\sum^{n}_{i=1}|a_i-b_i|$ 最小。
• 给定两个长度为 n 的数组 a, b，你现在可以对 a 的元素进行两种操作。花费 x 的代价让 ai 变为 ai + 1，或花费 y 的代价让 ai 变为 ai − 1。你可以先对 a 进行一次重排再开始操作，求使序列变成 b 的最小代价。
• 给定 n 对数 (ai, bi)(ai ⩾ bi)，你要从每对数中选择一个，并给选出来的数乘上 +1或 − 1。要求乘 +1 的次数恰好为 $⌊ n /2 ⌋$，其他均是乘 −1。 如何才能使得所有选出来的数的和最小？link
• n 个数对 (Li, Ri)，定义 $F_i=\lfloor \frac{\prod_{j=1}^{i-1}L_j}{R_i} \rfloor$ ，求一个最小化 max{Fi} 的排列。link
• 有 n 头牛在数轴上，第 i 头牛在 Ti 吃花，每分钟会吃掉 Di 朵花。你现在需要把这些牛送回位于原点的家，可惜的是你每次只能赶一头牛回家，例如你需要花 2Ti 的时间把第 i 头牛赶回家。 注意一旦开始赶第 i 头牛，那么他就会立刻停止吃花，而其他还没回家的牛不会受到影响。问如何赶牛回家可以使被牛吃掉的花最少。link
• n 头奶牛，第 i 头奶牛的体重为 Wi > 0，力量为 Si，定义第 i 头奶牛的压扁程 度 Fi = $\sum^{i-1}_{j=1}W_i-S_i$ 现在你可以重排这些奶牛，使这些奶牛中最大的压扁程度最小。link
• 给定 n 个数，将他们按任意顺序拼接成一个数，使这个数最大。link
• 现在要将 n 块硬盘全部格式化，硬盘初始都是满的，容量为 ai，格式化后容量会变为 bi。硬盘格式化时会清除数据，所以需要把原先的数据暂存到其他硬盘或外部空间。数据可以任意切分，求需要借助的最小外部空间大小。link

反悔贪心

此类贪心本质是费用流退流。发现曾经的决策不优时反悔，将所有不优决策都反悔即得到最优答案

• 数轴上有 n ⩽ $10^5$ 个点，第 i 个点的坐标是 xi，你可以花 ti 的时间得到 1 的价值（每个点最多一次）。 问从原点出发，使用时间不超过 m 可以得到的最大价值。link
• 给定一个由 ‘(’, ‘)’, ‘?’ 组成的字符串，对于第 i 个问号，你可以花费 ai 的代价 把它变成一个 ‘(’，也可以花费 bi 的代价把它变成一个 ‘)’。 问将字符串变为合法括号序列的最小代价。link
• 有 n 个任务，每个任务都需要 1 单位时间完成，同一时刻只能完成最多一个任 务。 其中，第 i 个任务必须在时间 Di 或以前完成，任务的收益是 Pi，问可以获得 的最大收益是多少。link
• 有 n 个建筑，第 i 个建筑需要 Ti 的时间修复，且必须在 Si 之前修复完成，同 一时刻只能修复一个建筑，求最多能够修复多少建筑。link
• 已知接下来 N 天的股票价格 p，每天你可以买进一股股票，或者卖出一股股票， 或者什么也不做。N 天之后你拥有的股票数量应为 0，问这 N 天内能最多能够赚多 少钱。link
• 有 n 头奶牛，第 i 头奶牛有原价 Pi 和使用优惠券后的价格 Ci，问有 K 张优惠 券的情况下，花不超过 M 的钱能买到的最大奶牛数量。 优惠券只能在每头奶牛身上使用一次。link
• 有 n 个人，第 i 个人的当前得分是 Ai ，他希望自己的得分 ⩾ Bi。 你可以任意交换两个学生的分数，问在保证所有人的得分都满足条件的情况下， 最多可以有多少人的分数不发生改变，无解输出 ‘-1’ link