6.1 区间问题
题目：给定 \(n\) 个闭区间 \([l_i,r_i]\)，在数轴上选出最少数量的点，使得每个区间至少包含一个被选择的点。\(1\le n\le 10^5,-10^9\le l_i,r_i\le 10^9\)。
思路：
贪心的想法是很显然的：先将所有区间按左端点排序。定义 \(L=l_1,R=r_1,cnt=1\)，重复以下步骤直到遍历完所有区间：
- 若第 \(i\) 个区间被区间 \([L,R]\) 包含，即 \(L\le l_i\le R\)，则将这两个区间合并，令 \(L=l_i,R=\min(R,r_i)\)（相当于在区间 \([l_i,\min(R,r_i)]\) 中选一个点）。
- 否则将 \(L\) 更新为 \(l_i\)，\(R\) 更新为 \(r_i\)，\(cnt\) 增加 \(1\)。
最终的答案即为 \(cnt\)。
这样，我们就可以让每个被选到的点都属于尽可能多的区间。时间复杂度 \(O(n\log n)\)。
贪心思路的证明：
显然，上述贪心算法一定满足题目的要求。我们只需要证明 \(cnt\) 最小即可。
不妨设通过算法上述所得到点为 \(d_1,d_2,\cdots,d_{cnt}\)。令 \(A_i\) 表示第 \(i\) 个区间，设 \(d_1\in A_1,A_2,\cdots,A_i\)。假设在执行算法第一步的过程中，我们直接跳至下一个区间，使得 \(d_1'\in A_1,A_2,\cdots,A_j\;(1\le j<i)\)，之后再继续按原来的算法执行。设这样得到的点数为 \(cnt'\)。由于 \(A_{j+1}\sim A_{i}\) 至少还需要一个点，假设 \(A_{j+1}\sim A_i\) 的区间并为 \([L,R]\)， 根据算法第二步有 \(R<l_{i+1}\)，又因为我们已经按区间左端点排序，所以 \(A_{j+1}\sim A_i\) 不可能再与任何一个区间合并，那么就有 \(cnt'\ge cnt\)（取等当且仅当 \(cnt=n\)），所以根据上述算法求出的 \(cnt\) 一定为最小值。
得证。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5+10;
int n, cnt = 1;
pii a[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i].first, &a[i].second);
sort(a+1, a+n+1);
int L = a[1].first, R = a[1].second;
for (int i = 2; i <= n; ++i) {
int L_ = a[i].first, R_ = a[i].second;
if (L <= L_ && L_ <= R) L = L_, R = min(R_, R);
else L = L_, R = R_, cnt ++;
}
printf("%d\n", cnt);
return 0;
}
题目：给定 \(n\) 个闭区间 \([l_i,r_i]\)，选择尽可能多的区间使得这些区间两两不相交，输出最大数量。\(1\le n\le 10^5,-10^9\le l_i,r_i\le 10^9\)。
思路：显然这道题与 AcWing 905. 区间选点 的答案是一模一样的。
题目：给定 \(n\) 个闭区间 \([l_i,r_i]\)，将这些区间分成尽量少的组，使得每组内部的区间两两没有交集。\(1\le n\le 10^5,-10^9\le l_i,r_i\le 10^9\)。
思路：
题目可以转化为：计算出一个点最多被几个区间包含（因为这些区间一定不能分在一组）。
令 \(cnt\) 表示当时点的区间数量。我们可以分别将 \(l_i,r_i\) 从小到大排序，并按从小到大的顺序遍历 \(l,r\) 数组，遇到 \(l_i\) 则 \(cnt\) 增加 \(1\)，遇到 \(r_i\) 则 \(cnt\) 减少 \(1\)。\(cnt\) 在此过程中的最大值即为答案。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n, cnt = 0, ans;
int start[N], close[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d%d", &start[i], &close[i]);
sort(start+1, start+n+1), sort(close+1, close+n+1);
int i = 1, j = 1;
while (i <= n || j <= n) {
if (start[i] <= close[j] && i <= n) cnt ++, i ++;
else if (j <= n) cnt --, j ++;
ans = max(ans, cnt);
}
printf("%d\n", ans);
return 0;
}
题目：给定一个区间 \([s,t]\) 和 \(n\) 个区间 \([l_i,r_i]\)，在这 \(n\) 个区间选择尽可能少的区间使得这些区间能够完全覆盖区间 \([s,t]\)，若无解则输出 -1。\(1\le n\le 10^5,-10^9\le l_i,r_i\le 10^9,-10^9\le s\le t\le 10^9\)。
思路：
贪心算法：先将 \(n\) 个区间按左端点排序，重复以下步骤直到遍历完所有区间：
- 找到第一个覆盖了 \([s,t]\) 且右端点最大的区间（即 \(l_i\le s,r_i\ge s\) 且 \(r_i\) 最大），所需区间增加 \(1\)，若找不到这样的区间，则无解；
- 若 \(r_i\ge t\) 则说明已经找到答案，退出循环；否则令 \(s=r_i\)。
证明比较显然，因为在剩下所有的能覆盖 \([s,t]\) 的区间中，右端点最大的区间所能覆盖的部分更多，若选择其他区间则一定不优于根据贪心算法求得的解。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5+10;
int n, s, t, ans;
bool check;
pii a[N];
int main() {
scanf("%d%d%d", &s, &t, &n);
for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i].first, &a[i].second);
sort(a+1, a+n+1);
for (int i = 1; i <= n; ++i) {
int j = i, r = - 2e9;
while (j <= n && a[j].first <= s) r = max(r, a[j].second), j ++;
if (r < s) {ans = -1; break;}
ans ++;
if (r >= t) {check = 1; break;}
s = r;
i = j-1;
}
if (!check) ans = -1;
printf("%d\n", ans);
return 0;
}
6.2 Huffman 树
题目：有编号为 \(1\sim n\) 的 \(n\) 堆石子，第 \(i\) 堆石子的质量为 \(a_i\)。现在要将这 \(n\) 堆石子合为一堆，合并任意两堆的代价是这两堆的石子质量之和，求出合并的最小总代价。\(1\le n\le 10000,1\le a_i\le 20000\)。
思路：合并果子是经典的 Huffman 树模型，其贪心思路很简单：每次取出两个最小值，将它们合并，直到只剩一堆石子。这个过程可以用小根堆实现，时间复杂度 \(O(n\log n)\)。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n, sum;
priority_queue<int, vector<int>, greater<int>> heap;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int x; scanf("%d", &x);
heap.push(x);
}
while (heap.size() > 1) {
int a = heap.top(); heap.pop();
int b = heap.top(); heap.pop();
sum += a+b;
heap.push(a+b);
}
printf("%d\n", sum);
return 0;
}
6.3 排序不等式
题目：有 \(n\) 个人排队打水，第 \(i\) 个人打水的时间为 \(t_i\)，求出所有人的最小等候时间之和。\(1\le n\le 10^5,1\le t_i\le 10^4\)。
思路：
贪心思路：先将 \(t\) 数组从小到大排序，令 \(s_i=\sum_{j=1}^{i-1}t_j\)，则答案即为 \(\sum_{i=1}^n s_i\)。
证明：
假设我们将 \(t\) 数组从小到大排序后，交换两个数 \(a_i,a_j\;(i<j)\) 的位置，令 \(s_i'=\sum_{j=1}^{i-1} t_j'\)，那么由于 \(a_j\ge a_i\)，则有 \(s'_{i+1}\ge s_{i+1},s'_{i+2}\ge s_{i+2},\cdots,s'_{j}\ge s_{j}\)。所以 \(\sum_{i=1}^ns'_i\ge\sum_{i=1}^ns_i\)，即交换后的答案一定不优于原来的答案。
得证。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int t; ll sum;
int a[N];
ll s[N];
int main() {
scanf("%d", &t);
for (int i = 1; i <= t; ++i) scanf("%d", &a[i]);
sort(a+1, a+t+1);
for (int i = 1; i <= t; ++i) {
s[i] = s[i-1]+a[i-1];
sum += s[i];
}
printf("%lld\n", sum);
return 0;
}
6.4 绝对值不等式
题目：在一条数轴上有 \(n\) 个点 \(a_i\)，在数轴上选出一个点 \(c\)，使得 \(\sum_{i=1}^n |c-a_i|\) 最小。\(1\le n\le 10^5,1\le a_i\le 40000\)。
思路：
贪心思路：先将 \(a\) 数组从小到大排序，令 \(c=a_{\lfloor n/2 \rfloor+1}\) 即可。
证明：
我们先考虑只有 \(2\) 个点的情况。分类讨论：
- \(c<a_1\)：题目所求为 \((a_1-c)+(a_2-c)=(a_2-a_1)+2(a_1-c)\)；
- \(a_1\le c\le a_2\)：题目所求为 \((c-a_1)+(a_2-c)=a_2-a_1\)；
- \(c>a_2\)：题目所求为 \((c-a_1)+(c-a_2)=(a_2-a_1)+2(c-a_2)\)。
显然当 \(a_1\le c\le a_2\) 时，题目所求最小。在数轴上画出来，可以更好地理解。
类似地，只有 \(3\) 个点时，\(c=a_2\) 时最小。
这两种情况可以推广至 \(n\) 个点的情况，即：若 \(n\) 为偶数，则 \(a_{n/2}\le c\le a_{n/2+1}\)；若 \(n\) 为奇数，则 \(c=a_{\lfloor n/2\rfloor+1}\)。
得证。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n, t, sum;
int a[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
sort(a+1, a+n+1);
t = a[n/2+1];
for (int i = 1; i <= n; ++i) sum += abs(t-a[i]);
printf("%d\n", sum);
return 0;
}
6.5 推公式
题目：有 \(n\) 头奶牛，第 \(i\) 头的重量为 \(w_i\)，强壮程度为 \(s_i\)。这些奶牛要表演叠罗汉，一头牛的风险值 \(d_i\) 为它头上所有牛的总重量减去它的身体强壮程度的值。请你确定一种方案，使得所有奶牛的风险值的最大值尽可能小，输出这个值。\(1\le n\le 5\times 10^4,1\le w_i\le 10^4,1\le s_i\le 10^9\)。
思路：
考虑叠罗汉时相邻的两头奶牛 \(i,j\)。设放在 \(i,j\) 上面的所有牛的总重量为 \(W\)。分类讨论：
- \(i\) 放在 \(j\) 上面：此时 \(d_i=W-s_i,d_j=W+w_i-s_j\)；
- \(j\) 放在 \(i\) 上面：此时 \(d_i=W+w_j-s_i,d_j=W-s_j\)。
考虑什么时候 \(i\) 放在 \(j\) 上面更优。则 \(\max(W-s_i,W+w_i-s_j)\le \max(W+w_j-s_i,W-s_j)\)。由于 \(w_i,w_j>0\)，所以 \(W-s_i<W+w_j-s_i,W+w_i-s_j>W-s_j\) 。
那么当 \(W+w_i-s_j\le W+w_j-s_i\) ，即 \(w_i+s_i\le w_j+s_j\) 时，\(i\) 放在 \(j\) 上面更优。
我们可以将所有牛按 \(t_i=w_i+s_i\) 从小到大排序，\(t_i\) 小的牛放在上面，若有 \(t_i\) 相同的牛，则 \(s_i\) 小的放在上面。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 5e4+10;
int n;
ll ans = -1e18, sum;
pii c[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int w, s; scanf("%d%d", &w, &s);
c[i].first = w+s, c[i].second = s;
}
sort(c+1, c+n+1);
for (int i = 1; i <= n; ++i) {
sum -= (ll)c[i].second;
ans = max(ans, sum);
sum += (ll)c[i].first;
}
printf("%lld\n", ans);
return 0;
}