「JOI 2023 Final」宣传 2 题解

题目分析

给定 $N$ 位居民，第 $i$ 位居民住在位置 $X_i$，影响力为 $E_i$。如果给居民 $i$ 送书，那么所有满足 $|X_i - X_j| \leq E_i - E_j$ 的居民 $j$ 都会买书。求最少需要给多少居民送书，才能让所有居民都有书。

代码思路

核心转化

将条件 $|X_i - X_j| \leq E_i - E_j$ 转化为：

• 居民 $i$ 能覆盖居民 $j$ 当且仅当：$$X_i - E_i \leq X_j - E_j \quad \text{且} \quad X_j + E_j \leq X_i + E_i $$

定义：

• $L_i = X_i - E_i$（左边界）
• $R_i = X_i + E_i$（右边界）

则居民 $i$ 能覆盖居民 $j$ 当且仅当区间 $[L_j, R_j]$ 被区间 $[L_i, R_i]$ 包含。

算法步骤

1. 预处理：为每个居民计算 $L_i$ 和 $R_i$
2. 排序：按 $R_i$ 从大到小排序，$R_i$ 相同时按 $L_i$ 从大到小排序
3. 贪心选择：
   • 维护变量 mi 记录当前已覆盖的最左边界
   • 遍历排序后的居民，如果当前居民的 $L_i > mi$，则选择该居民，并更新 mi = L_i

代码解析

#include <bits/stdc++.h>
using namespace std;
long long n, ans, x, y, mi = -1000000000000000000;
struct s {
    long long l, r;
} a[1000000];

// 排序规则：按r从大到小，r相同时按l从大到小
bool cmp(s a, s b) {
    if (a.r == b.r)
        return a.l > b.l;
    else
        return a.r > b.r;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x >> y;
        a[i].l = y - x;  // L = X - E
        a[i].r = y + x;  // R = X + E
    }

    sort(a + 1, a + n + 1, cmp);

    for (int i = 1; i <= n; i++)
        if (a[i].l > mi) {  // 如果当前居民左边界大于已覆盖范围
            ans++;          // 选择该居民
            mi = a[i].l;    // 更新已覆盖的最左边界
        }

    cout << ans;
    return 0;
}

算法原理

排序策略的意义

• 按 $R_i$ 从大到小排序：优先处理覆盖范围大的居民
• $R_i$ 相同时按 $L_i$ 从大到小排序：在覆盖范围相同的情况下，优先处理左边界更靠右的居民

贪心选择的逻辑

条件 if (a[i].l > mi) 的含义：

• 如果当前居民的左边界 $L_i$ 大于已覆盖的最左边界 mi，说明这个居民无法被已选择的居民覆盖
• 因此需要选择这个居民来扩展覆盖范围

更新 mi = a[i].l 的含义：

• 记录已选择居民中的最小左边界
• 后续居民如果左边界小于等于这个值，说明可以被已选择的居民覆盖

正确性说明

这个解法基于以下观察：

1. 如果居民 $i$ 能覆盖居民 $j$，那么 $L_i \leq L_j$ 且 $R_i \geq R_j$
2. 按 $R_i$ 降序排序后，如果当前居民的 $L_i$ 大于之前所有选择居民的 $L_i$，说明它不能被任何已选择的居民覆盖
3. 因此必须选择这个居民来确保覆盖

复杂度分析

• 时间复杂度：$O(N \log N)$，主要来自排序
• 空间复杂度：$O(N)$，存储居民数据

该解法通过巧妙的排序和贪心策略，将复杂的最优化问题转化为简单的线性扫描，实现了高效求解。