防晒

1 题目描述

有 $C$ 头奶牛进行日光浴，第 $i$ 头奶牛需要 $\min\text{SPF}[i]$ 到 $\max\text{SPF}[i]$ 单位强度之间的阳光。

每头奶牛在日光浴前必须涂防晒霜，防晒霜有 $L$ 种，涂上第 $i$ 种之后，身体接收到的阳光强度就会稳定为 $\text{SPF}[i]$，第 $i$ 种防晒霜有 $\text{cover}[i]$ 瓶。

求最多可以满足多少头奶牛进行日光浴。

输入格式

第一行输入整数 $C$ 和 $L$。

接下来的 $C$ 行，按次序每行输入一头牛的 $\min\text{SPF}$ 和 $\max\text{SPF}$ 值，即第 $i$ 行输入 $\min\text{SPF}[i]$ 和 $\max\text{SPF}[i]$。

再接下来的 $L$ 行，按次序每行输入一种防晒霜的 $\text{SPF}$ 和 $\text{cover}$ 值，即第 $i$ 行输入 $\text{SPF}[i]$ 和 $\text{cover}[i]$。

每行的数据之间用空格隔开。

输出格式

输出一个整数，代表最多可以满足奶牛日光浴的奶牛数目。

数据范围

$1 \le C, L \le 2500$, $1 \le \min\text{SPF} \le \max\text{SPF} \le 1000$, $1 \le \text{SPF} \le 1000$。

输入样例：

1
2
3
4
5
6

3 2
3 10
2 5
1 5
6 2
4 1

输出样例：

1

2

2 解析

启发式策略：按照 $\max\text{SPF}$ 右端点从小到大排序，然后枚举每头牛，每次选择区间内最小的防晒霜。

证明方法有两种，蓝书上的范围缩放和 y 总的二分图反证不存在增广路径。

我简略介绍一下两种证明方法，具体大家可以去参考这两位佬的详细证明过程。

范围缩放

每瓶防晒霜是否可用，取决于 $[\min\text{SPF}[i], \max\text{SPF}[i]]$。

由于牛牛们按照 $\max\text{SPF}$ 从小到大排好序了，因此每一个不高于当前奶牛 $\max\text{SPF}$ 的防晒霜，都不会高于后续奶牛的 $\max\text{SPF}$。

对于当前奶牛可用的任意两瓶防晒霜 $x$ 和 $y$，如果 $\text{SPF}[x] < \text{SPF}[y]$：

那么后面其他奶牛与该两瓶防晒霜的关系有：

1. 两瓶都能用
2. 两瓶都不能用
3. $x$ 不能用，$y$ 能用

因此，当前奶牛选择较小的 $x$ 对于整体问题的影响显然比选择较大的 $y$ 更好。

另外，每头奶牛对答案的贡献至多为 1。即使放弃当前奶牛，留下防晒霜给后面的奶牛，对答案的贡献也不会变大。

综上，得证该策略为正确策略。

这个证明不细致 by rainboy 2025-11-19

增广路径

将所有区间看做二分图的一个顶点集，将所有防晒霜的点看做另一个顶点集。

证明对于当前牛选择该防晒霜的策略下，不存在一条增广路径即可。

显然，增广路径的匹配是区间、点交替匹配的，以当前防晒霜的点为起点寻找增广路径（终点一定是未匹配的区间的顶点）：

1. 如果向后寻找增广路径，显然会使得路径变短，违背了定义。
2. 如果向前寻找增广路径，根据我们枚举的顺序，终点一定是已匹配的区间的顶点，违背了定义。

因此不存在增广路径，所以该启发式策略一定是最优策略。

这个证明使用了: 最大匹配问题,确实是个好的证明,使用 数学方法: 转换

第三个证明用交换论证，见下文交换论证。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

cin >> n >> m;
spfs[1001] = n; 
for (int i = 0; i < n; i ++ ) cin >> seg[i].l >> seg[i].r;
for (int i = 0, x, t; i < m; i ++ )
{
    cin >> x >> t;
    spfs[x] += t;
}
sort(seg, seg + n);
int res = 0;
for (int i = 0; i < n; i ++ )
{
    auto spf = spfs.lower_bound(seg[i].l);
    if (spf -> first <= seg[i].r)
    {
        res ++ ;
        if ( -- spf -> second == 0)
        {
            spfs.erase(spf);
        }
    }
}
cout << res << endl;

3 交换论证

在算法问题中，我们经常遇到需要在数轴上将一组区间与一组点进行配对，以实现配对数量最大化的场景。一个直观的贪心策略是：优先考虑那些“限制性”更强的区间。本文将详细阐述并证明一个经典的贪心算法：将所有区间按右端点升序排序，然后依次为每个区间选择其范围内最靠左的可用点进行配对。我们将使用交换论证（Exchange Argument）方法，一步步揭示该策略为何能够导出全局最优解。

3.1 问题重述

给定数轴上的一组区间集合 $I = \{i_1, i_2, \dots, i_m\}$ 和一组点集合 $P = \{p_1, p_2, \dots, p_n\}$。

• 每个区间 $i_k$ 表示为 $[l_k, r_k]$。
• 一个区间 $i_k$ 和一个点 $p_j$ 可以配对，当且仅当 $l_k \le p_j \le r_k$。

目标是找到一个规模最大的配对集合 $M \subseteq I \times P$，满足以下条件：

1. 集合 $M$ 中的每个区间至多被使用一次。
2. 集合 $M$ 中的每个点至多被使用一次。
3. 对于 $M$ 中的任一配对 $(i_k, p_j)$，必须满足 $p_j \in [l_k, r_k]$。

3.2 贪心策略

我们提出以下贪心策略来解决此问题：

1. 排序区间： 将所有区间 $i_k \in I$ 按照其右端点 $r_k$ 从小到大进行升序排序。
2. 迭代配对： 依次遍历排序后的区间。对于当前区间 $i = [l, r]$，从所有它能覆盖且尚未被配对的点中，选择位置最靠左（坐标值最小）的点 $p^*$ 与之配对。
3. 更新状态： 如果找到了这样的点 $p^*$，则记录配对 $(i, p^*)$，并将点 $p^*$ 标记为“已配对”。处理下一个区间，直到所有区间都被考察完毕。

策略核心思想： 按右端点排序，意味着我们优先处理那些“即将结束”的区间。为这些区间选择最左边的点，是为了将“更靠右”的点资源留给那些右端点更大的区间，因为后者有更大的灵活性去覆盖靠右的点。

3.3 正确性证明：交换论证

我们将使用经典的交换论证 (Exchange Argument) 来证明上述贪心策略的正确性。证明的核心是表明，贪心算法做出的每一步选择，都可以被包含在某个最优解中。

设 $S_G$ 是由我们的贪心策略产生的配对集合。 设 $S_{OPT}$ 是任意一个最优解（即规模最大的配对集合）。

我们的目标是证明 $|S_G| = |S_{OPT}|$。

3.4 核心引理：贪心选择性质 (Greedy Choice Property)

贪心策略的第一步选择是“安全”的，即它存在于某个最优解中。

证明： 令贪心策略做出的第一个选择为 $g_1 = (i_1, p_1)$，其中：

• $i_1$ 是所有区间中右端点 $r_1$ 最小的区间。
• $p_1$ 是 $i_1$ 所能覆盖的、所有可用点中最靠左的点。

现在，我们来分析最优解 $S_{OPT}$：

情况 1：$S_{OPT}$ 包含了贪心选择 $g_1$ 如果 $(i_1, p_1) \in S_{OPT}$，那么贪心选择已经是该最优解的一部分，引理成立。

情况 2：$S_{OPT}$ 不包含贪心选择 $g_1$ 如果 $(i_1, p_1) \notin S_{OPT}$，则必然存在以下两种子情况之一：

子情况 2a：$i_1$ 在 $S_{OPT}$ 中未被配对 由于 $S_{OPT}$ 是最优解，如果点 $p_1$ 也未被配对，我们可以直接将 $(i_1, p_1)$ 加入 $S_{OPT}$，得到一个规模更大的解，这与 $S_{OPT}$ 的最优性矛盾。因此，$p_1$ 必然在 $S_{OPT}$ 中与另一个区间 $i'_1$ 配对，即 $(i'_1, p_1) \in S_{OPT}$。

我们可以构造一个新的解 $S'_{OPT}$：

子情况 2b：$i_1$ 在 $S_{OPT}$ 中与另一个点 $p'_1$ 配对 即 $(i_1, p'_1) \in S_{OPT}$，且 $p'_1 \ne p_1$。 同时，由于 $p_1$ 是一个必须考虑的点（否则可加入 $(i_1, p_1)$ 提升解），它必然在 $S_{OPT}$ 中与另一个区间 $i'_1$ 配对，即 $(i'_1, p_1) \in S_{OPT}$。

我们已知：

1. 根据贪心选择，$p_1$ 是 $i_1$ 覆盖的最左点，所以 $p_1 < p'_1$。
2. 根据贪心选择，$i_1$ 是右端点最小的区间，所以 $r_{i_1} \le r_{i'_1}$。

现在，我们执行一次交换操作，构造新解 $S'_{OPT}$：

新解 $S'_{OPT}$ 的规模与 $S_{OPT}$ 相同。我们只需验证新的配对 $(i'_1, p'_1)$ 是否合法，即 $p'_1$ 是否在区间 $i'_1 = [l_{i'_1}, r_{i'_1}]$ 内。

• 验证左边界：

  • 因为 $(i'_1, p_1) \in S_{OPT}$ 是合法配对，所以 $l_{i'_1} \le p_1$。
  • 我们已知 $p_1 < p'_1$。
  • 因此，$l_{i'_1} \le p_1 < p'_1$，左边界条件 $l_{i'_1} \le p'_1$ 成立。

• 验证右边界：

  • 因为 $(i_1, p'_1) \in S_{OPT}$ 是合法配对，所以 $p'_1 \le r_{i_1}$。
  • 我们已知 $r_{i_1} \le r_{i'_1}$。
  • 因此，$p'_1 \le r_{i_1} \le r_{i'_1}$，右边界条件 $p'_1 \le r_{i'_1}$ 成立。

两个边界条件均成立，证明新配对 $(i'_1, p'_1)$ 是合法的。 我们成功地将任意一个不含 $g_1$ 的最优解 $S_{OPT}$ 转化为了一个包含 $g_1$ 的、规模相同的新最优解 $S'_{OPT}$。

综上所述，贪心选择 $g_1$ 是一个安全选择。

3.5 最优子结构与归纳

证明了第一个贪心选择是安全的之后，我们实际上将原问题转化为了一个规模更小的子问题。 将 $i_1$ 和 $p_1$ 从各自的集合中移除，剩下的问题是在 $I \setminus \{i_1\}$ 和 $P \setminus \{p_1\}$ 中寻找最大配对。我们已经证明，存在一个最优解，其剩余部分 $S'_{OPT} \setminus \{g_1\}$ 正是这个子问题的最优解。

由于原问题具有最优子结构 (Optimal Substructure)，并且我们证明了每一步的贪心选择都是安全的，通过数学归纳法可以得出，将此贪心策略执行到底，所得到的解 $S_G$ 的规模必然与最优解 $S_{OPT}$ 的规模相等。

3.6 结论

通过严谨的交换论证，我们证明了“按右端点排序，为每个区间选择最左边的可用点”这一贪心策略的正确性。它确保了在每一步决策时，都为后续的区间留下尽可能多的选择空间，从而导出全局最优解。这个例子是理解贪心算法设计和证明的经典范例。

4 相关题解

暂无相关题解