第11章　和定最值、极端构造与鸽巢原理

1. 和定最值

若若干正整数和固定，求某一项最小/最大，要先让其他项尽可能大/小，同时满足互异、倍数、排名等限制。例如 4 个互不相同的正整数和为 18，最小值尽可能小时，可取 1、2、6、9，合计 18，因此最小值能达到 1。若还有“必须连续”“最大值不超过某数”等条件，构造后都要逐条检查。

“每个都不同且相差最多不超过 1 倍”会限制大小关系；“最大项为第二大项的某范围”要转化为上界后再构造。

2. 最不利原则

问“至少取多少次才能保证”，先构造“还没保证”的最多情况，再加 1。

若有 $k$ 类物品，每类至多拿 $r-1$ 个仍可能没有 $r$ 个同类，则最坏情况为 $k(r-1)$，保证数量为 $k(r-1)+1$。例如 4 种颜色的球，每种最多先拿 2 个仍凑不出 3 个同色球，最坏拿 8 个；再拿 1 个就一定有 3 个同色球。若各类物品数量有限，则先按每类 $min(n_i,r-1)$ 个计算；某类拿完后，不能再假设这类还有库存。若算出的保证数量大于现有物品总数，说明现有物品不足以保证目标。

3. 鸽巢原理

把要分配的对象看作鸽子、类别看作鸽巢。$N$ 个对象分到 $k$ 个类别时，至少一个类别不少于 $\lceil N/k\rceil$；$\lceil x\rceil$ 表示不小于 $x$ 的最小整数。例如 10 人分到 3 个班，至少一个班有 $\lceil 10/3\rceil =4$ 人。年龄、专业、颜色、抽奖礼品都能套此结构，但要确认类别互不重叠且覆盖了题目所说的对象。

4. 反向构造

“至少多少人同时看过三项”可从“尽量把三项错开”构造；“至少有一店分到 8 箱”可先假设所有店最多 7 箱，再由总箱数推出店数上界。极值题常由否定目标开始构造。