写在开头

• 贪心问题难在如何想到做法+证明起来麻烦
• 区间贪心问题没思路可以先排序试试，按照左端点/右端点/双关键字排序
• 贪心思想：每次选择局部最优解，按照这种策略可以取得全局最优解，这种策略也决定了只有单峰值问题才可以用贪心（？待验证）
• 贪心证明：
  • 证明贪心解cnt是不是恰好等于最优解ans（怎么感觉贪心证明全是有些自指性的问题，证明我是我（以下方法待验证
    • 证明ans>=cnt
    • 证明ans<=cnt
    • 综上ans==cnt
    • 注意贪心解cnt的定义，只要算法符合要求，贪心解cnt一定是合法的方案，所以cnt合法的前提下，如果求最大那么ans显然>=cnt，如果求最小ans显然<=cnt
    • 然后用反证法证明另一边，注意贪心解cnt的定义
    • 要么就通过某种等价变换可以直接一步到位证明最优解ans一定可以等价变换为贪心解cnt，也就是ans==cnt
  • 反证法——假设最优解不是贪心解，然后证明这是不现实的
  • 数学归纳法

区间

区间选点

给定$N$个闭区间$[a_i,b_i]$，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点，输出选择的点的最小数量。

思路

• 将每个区间按照右端点从小到大进行排序
• ed值初始化为无穷小，从前往后枚举区间
• 如果遍历到的区间的左端点大于记忆区间的右端点（放有点），则把记忆区间更新成当前遍历的区间(只更新右端点，因为只在右端点放点)

证明

• 假设$ans$是最优解，$cnt$是可行解，显然有$ans \le cnt$
• 由于算法最后得出$cnt$个两两不相交的区间，覆盖每个区间至少需要$cnt$个点，因此$ans \ge cnt$

• 综上所述$ans = cnt$

• 证明：假设ans是最优解（最小值），cnt是贪心解

• 贪心解cnt实际上找到的点集实际上代表了一堆互不相交的区间，一个点代表着覆盖到了一个区间，这些区间互不相交且一定会被按顺序找到（其他区间由于算法性质是会被这些点集所覆盖到的
• ans <= cnt ：因为是最优解，显然这句话是对的
• ans >= cnt ：用到贪心解cnt的定义，用到反证法：
  • 假设ans < cnt，那么意味着存在一个解，这个解的点集数量比贪心解cnt少，在这种情况下还要满足贪心解cnt覆盖到的所有不相交的区间，显然这是不可能的，只要点集数量少于贪心解cnt就一定会有某个不相交区间没有被覆盖到，所以ans[HTML_REMOVED]=cnt成立
• 综上，ans=cnt，贪心解就是最优解

核心代码

struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return r < W.r;
    }
}range[N];

sort(range, range + n);

int res = 0, ed = -2e9;
for (int i = 0; i < n; i ++ )
    if (range[i].l > ed)
    {
        ed = range[i].r;        // 在当前区间的右端点放一个点
        res ++ ;
    }

printf("%d\n", res);

最大不相交区间数量

可以参考区间选点那题，二者在算法思路上是一致的

• 将每个区间按照右端点从小到大进行排序
• ed表示当前放置在数轴上的点的位置，开始初始化为无穷小，表示没有放置，此时数轴上没有点
• 依次遍历排序好的区间。如果区间的左端点大于当前放置点的位置，说明当前点无法覆盖区间，则把点的位置更新成该区间的右端点，表示在该区间的右端点放置一个新的点，同时更新点的个数

证明

• 假设$ans$是最优解，表示最多有$ans$个不相交的区间；$cnt$是可行解，表示算法求出个不相$cnt$交的区间，显然有$ans \ge cnt$
• 反证法证明$ans \le cnt$。假设$ans \gt cnt$，由最优解的含义知，最多有$ans$个不相交的区间，因此至少需要$ans$个点才能覆盖所有区间，而根据算法知，只需$cnt$个点就能覆盖全部区间，且$cnt < ans$，这与前边分析至少需要$ans$个点才能覆盖所有区间相矛盾，故$ans \le cnt$

• 综上所述$ans=cnt$

• 证明同上……，感觉这个问题就是上个问题的子问题……

• ans是最优解（最大值），cnt是贪心解，
• ans >= cnt，显然
• ans <= cnt，反证法，假设ans > cnt，意味着存在某个解比贪心解多至少一个不相交的区间，但如果存在一个这样的区间，贪心方法一定可以找到它，所以ans > cnt不成立，所以ans<=cnt成立（严谨性有些存疑，看海绵宝宝题解的证明图
• 综上，ans=cnt
• （上面两道题有点逻辑闭环的意味？
• （感觉重点在于贪心解cnt是如何定义的，也就是说贪心解cnt是由什么算法计算出来的，ans到底等不等于cnt的证明过程绝对要和算法过程挂钩，证明时绝对不能忽视算法内部的定义

核心代码

struct Range
{
    int l, r;
    bool operator< (const Range &W)const        
    {
        return r < W.r;         // 使sort()按右端点升序排序
    }
}range[N];

// main
sort(range, range + n);         // 按右端点升序排序

int res = 0, ed = -2e9;         // ed为无穷小
for (int i = 0; i < n; i ++ )
    if (ed < range[i].l)
    {
        // 找到一个无法由当前点覆盖的区间
        ed = range[i].r;         // 在数轴上放入新的点
        res ++ ;                // 更新数轴上点的个数
    }

区间分组

给定N个闭区间$[a_i,b_i]$，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。

思路

• 左端点排序，从前往后处理每个区间
• 判断能否将其放到某个现有的组中（将其左端点与组中最大右端点比较
  • 如果不可以，则开新组放入
  • 如果可以，则放进该组并更新该组的最大右端点

证明

• 假设$ans$是最优解，表示最少需要$ans$个组；$cnt$是可行解，表示算法找到$cnt$个组，显然有$ans \le cnt$
• 考虑在开辟第$cnt$个组的过程：算法此时已经开辟了$cnt-1$个组，组内区间两两不相交，组间区间有交集，且当前遍历区间的左端点均小于各组所有区间中最大的右端点，即当前遍历的区间一定与各组区间相交，此时必须要开辟新的组放入新的区间，因此至少需要$cnt$个组，即$ans \ge cnt$
• 综上所述$ans=cnt$

核心代码

struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return l < W.l;
    }
}range[N];

// main
sort(range, range + n);         // 按左端点升序排序

priority_queue<int, vector<int>, greater<int>> heap;        // 小根堆，保存每组的最大右端点
for (int i = 0; i < n; i ++ )
{
    if (heap.empty() || range[i].l <= heap.top()) heap.push(range[i].r);    // 比所有组最大右端点都小
    else {
        heap.pop();                 // 合并到右端点最小的组，并更新该组的最大右端点
        heap.push(range[i].r);
    }
}

printf("%d\n", heap.size());        // 小根堆元素个数为组数

说明

• range[i].l <= heap.top()等价于range[i].l <= min(heap)，表示比各组最大的右端点还要小，使得min的代价变为$O(1)$
• 小根堆内并没有真的存储各组区间，而只是存储各组的最大右端点，当区间的左端点比各组右端点都小时，说明都冲突，需要开辟新组；否则只需把右端点最小的组的右端点更新成当前区间的右端点

区间覆盖

给定$N$个闭区间$[a_i,b_i]$以及一个线段区间$[s,t]$，请你选择尽量少的区间，将指定线段区间完全覆盖。

思路

• 将所有区间按左端点从小到大排序
• 从前往后依次枚举每个区间，在所有能覆盖start的区间中选择右端点最大的区间，并将start更新成右端点的最大值

证明

• 假设$ans$是最优解，表示最少需要$ans$个区间；$cnt$是可行解，表示算法找到$cnt$个区间满足覆盖，显然有$ans \le cnt$
• 采用反证法证明$ans \ge cnt$
  • 假设最优解由$k$个区间组成，各区间按右端点从小到大排序，右端点依次记为$a_1,a_2,\cdots , a_k$，显然一定有$t \le a_k$，否则最优解没有覆盖到线段区间$[s,t]$的右端点$t$，不满足覆盖条件
  • 同理，假设算法求得$m(m>k)$个区间，各区间按右端点从小到大排序，右端点依次记为$b_1,b_2,\cdots , b_k,\cdots , b_m$，显然一定有$b_k < t \le b_m$
    • $t \le b_m$是为了满足覆盖条件
    • $b_k < t$是因为$b_k$不是最后一个区间的端点，如果$b_k \le t$，则
  • 考虑最优解和贪心算法各自获得的第1个区间的右端点$a_1$和$b_1$，由于贪心算法选取右端点距离起点$s$最大的区间，故一定有$a_1 \le b_1$
  • 贪心算法又以$b_1$为起点，找一个右端点距离$b_1$最大的区间，最优解选取的第2个区间的右端点$a_2$不可能超过$b_2$，否则存在一个区间的长度$a_2 - a_1$大于$b_2-b_1$，这与贪心算法矛盾，故一定有$a_2 \le b_2$
  • 同理一定有$a_k \le b_k$，由于$b_k < t$，故$a_k < t$，这说明最优解没有覆盖线段区间$[s,t]$，矛盾
  • 故$ans \ge cnt$
• 综上所述$ans=cnt$
• 证明：
• ans<=cnt显然
• ans>=cnt：反证法
  • 假设ans<cnt，那么ans找到的区间里必然存在至少一个右端点比cnt选法延伸得长的区间（先不考虑这个区间左端点如何，后面会证明），然后从前往后枚举证明
    • ①如果ans选中的区间右端点延申没有cnt选中的区间长，那么完全可以无痛替换为cnt选中的区间（我们将这个替换操作记为X操作），对ans的结果没什么区别；
    • ②如果ans选中的区间右端点延申比cnt选中的区间长，那么分两种情况（但是有一个共同前提，假设我们是第一次遇到情况②，且因为X操作前面的情况①区间已经等效替换为了与cnt相同的区间），
      • Ⅰans选中的区间左端点接得上cnt选中的上一个区间，那么在这种前提下，贪心算法一定可以找得到这个区间，既然它没有被贪心算法找到，也就说明这个区间不存在；
      • Ⅱans选中的区间接不上cnt选中的区间，因为ans前面的区间已经被X操作替换成了cnt的区间，所以如果它接不上，它一定是不符合原题要求的区间，所以它更不应该存在
      • 也就是说“ans选中的区间右端点延申比cnt选中的区间长”这种情况一定不会存在
  • 我们已经证明出了“ans中一定不存在一个右端点延申比cnt选中的区间长”的情况，那么ans就一定不会小于cnt
  • 所以ans>=cnt
  • （这是一坨什么玩意
• 综上ans==cnt

核心代码

struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return l < W.l;
    }
}range[N];

// main
sort(range, range + n);         // 按左端点升序排序

int res = 0;
bool success = false;
for (int i = 0; i < n; i ++ )
{
    // 贪心算法核心部分
    int j = i, r = -2e9;
    while (j < n && range[j].l <= st)//遍历然后找到所有覆盖到起点的区间中，右端点最大的那个区间的右端点值
    // 保证覆盖起点（起点是会变化的）
    {
        r = max(r, range[j].r);     // 选取距离起点最大的点（实际上只需看右端点的大小，因为起点是固定的，不影响max的选取）
        j ++ ;
    }

    // 如果所有区间的右端点都比起点小，则无解
    if (r < st)
    {
        res = -1;
        break;
    }

    res ++ ;

    // 满足条件，结束
    if (r >= ed)
    {
        success = true;
        break;
    }

    st = r;     // 更新起点
    i = j - 1;  // 指针直接跳转到合适的地方迭代（双指针法）
}

if (!success) res = -1;
printf("%d\n", res);

Hoffman树

有$n$个结点，每次合并两个结点需要消耗两个结点值之和的能量，求一种能量消耗最少的方案，使得所有结点合并成一个。

这里与合并石子的区别在于，合并石子只能合并相邻的两堆，而这里允许任意两个合并，并不一定是相邻的。

思路

每次选取最小的两个结点合并，直至全部合并成一个结点
合并过程构造了一颗树，合并所需的总体力=(叶子结点的值*到达根节点的路径长度)之和，也就是(每堆果子数*被移动的次数)之和

证明

命题1：最小的两个点深度一定最深，且可以互为兄弟（后面半句话意味着它们在同一层，并不是说它们一定得是兄弟）

命题2：最优树用一个非叶结点代替这两个结点后，依旧是最优树

命题1一定成立，否则将值最小的点与深度最深的点交换，一定会使总和减少，与最优树定义矛盾。

证明命题2等价于证明这是最优子结构。考虑等式$f(k+1)=f(k)+a+b$，其中$a$和$b$是$k+1$个结点构成的树中，值最小的两个。在$k$个结点构成的树中，用一个新的叶节点代替了这两个结点。假设选取的不是$a$和$b$，显然新选结点的和会大于之前选的结点的和，故得到的不是最优树，因此这样构造的树一定是最优树，故满足最优子结构

核心代码

priority_queue<int, vector<int>, greater<int>> heap;        // 用小根堆存储元素，加快最小值的查找

int res = 0;
while (heap.size() > 1)         // 合并成1个
{
    int a = heap.top(); heap.pop();
    int b = heap.top(); heap.pop();
    res += a + b;
    heap.push(a + b);
}

排队打水

有 $n$ 个人排队到 $1$ 个水龙头处打水，第 $i$个人装满水桶所需的时间是 $t_i$，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？

第$1$个人等待的时间是$0$，第$2$个人等待的时间是$t_1$，第$3$个人等待的时间是$t_1+t_2$，…，第$n-1$个人等待的时间是$t_1+t_1+\cdots + t_{n-2}$，第$n$个人等待的时间是$t_1+t_1+\cdots + t_{n-1}$

因此所有人的等待时间之和：

$$0+(t_1)+(t_1+t_2)+(t_1+t_2+t_3)+\cdots + (t_1 + t_2 + \cdots + t_n-1)=t_1(n-1)+t_2(n-2)+\cdots + t_{n-1}$$

思路

当$t_1,t_2,\cdots , t_n$按升序排列时，所有人的等待时间最少。

证明

反证法：假设$i<j$且$t_i \gt t_j$，则可以交换二者，总时间会减少，说明原来不是最少的时间，矛盾。

核心代码

sort(t, t + n);         // 默认升序排序
reverse(t, t + n);      // 改成降序

long long res = 0;
for (int i = 0; i < n; i ++ ) res += t[i] * i;

货仓选址

数轴上有$n$个点，在数轴上找一个点，使得那$n$个点到这个点的距离之和最小

假设升序排序后的$n$个数为$x_1, x_2, \cdots,x_n$

总距离可表示为

$$\begin{aligned} f\left( x \right) &=\left| x_1-x \right|+\left| x_2-x \right|+\cdots +\left| x_n-x \right| \\\ &=\left( \left| x_1-x \right|+\left| x_n-x \right| \right) +\left( \left| x_2-x \right|+\left| x_{n-1}-x \right| \right) +\cdots \\\ &\geqslant \left( x_n-x_1 \right) +\left( x_{n-1}-x_2 \right) +\cdots \end{aligned}$$

由排序不等式知，当$n$是奇数时，当且仅当在中位数取到等号；当$n$是偶数，则当且仅当在两个中位数之间都能取到等号

核心代码

sort(a, a + n);

int res = 0;
for (int i = 0; i < n; i ++ ) res += abs(a[i] - a[n / 2]);      // q[n / 2]为中位数

说明

• 如果$n$是奇数，则n / 2是中位数下标
• 如果$n$是偶数，则n / 2是靠左的中位数下标，由于在$a_{n/2}$~$a_{n/2 + 1}$之间（包括端点）都能取到等号，故可以和奇数一致选取下标为n/2的数

耍杂技的牛

有$n$头牛，第$i$头牛的重量为$w_i$，强壮值为$s_i$，一头牛的危险系数定义为这头牛上边的重量之和减去这头牛的强壮值，求一种顺序，使得$n$头牛最大的危险系数最小

思路

按$w_i+s_i$升序排序

证明

假设$best$是最优解，表示最小的危险系数；$ans$是可行解，表示算法找到危险系数，显然有$best \le ans$

反证法证明$best \ge ans$。假设$w_i+s_i>w_{i+1} + s_{i+1}$，可得下表

各项同时去掉$w_1+w_2+\cdots +w_{i-1}$，得

各项同时加上$s_i + s_{i+1}$，得

由于$w_i+s_i \ge s_i$且$w_i+s_i \ge w_{i+1}+s_{i+1}$，故$w_i+s_i \ge \max\{s_i, w_{i+1}+s_{i+1} \}$，进而$\max \{ s_{i+1}, w_i + s_i \} \ge \max\{s_i, w_{i+1}+s_{i+1} \}$

故交换后$n$头牛的最大危险系数要么减少，要么不变，总之不会增加

假设最优解有满足这样条件的两头牛，则把它们交换后，最大危险系数会下降，与最优解的定义矛盾，故最优解一定满足这样按$w_i+s_i$升序排序的条件，即$best \ge ans$

综上所述$best=ans$

核心代码

typedef pair<int, int> PII;
PII cow[N];

// 读入
scanf("%d%d", &w, &s);
cow[i] = {w + s, w};    // first为二者和，second为重量

// main
sort(cow, cow + n);     // 按w+s升序排序

int res = -2e9, sum = 0;        // 初始化为无穷小
for (int i = 0; i < n; i ++ )
{
    int s = cow[i].first - cow[i].second, w = cow[i].second;    // 读取s和w
    res = max(res, sum - s);        // 更新最大危险系数
    sum += w;                      // 第0~i头牛的重量之和（由上到下）
}

说明

• 最上边的牛的危险系数不是$0$，而是$-s$

参考资料：y总直播，站内卢盼盼笔记