题解：AT_abc434_e [ABC434E] Distribute Bunnies

· · 题解

题意

有 n 只兔子，第 i 只兔子的坐标为 x_i，跳跃能力为 r_i。一次跳跃中，第 i 只兔子可以选择跳到位置 x_i - r_i 或 x_i + r_i。
若所有兔子各跳一次，求跳完后所有兔子所在的不同位置的最大可能数量（即尽量让兔子们不落在同一个位置）。

分析

问题可以转化为以下模型：
有 n 只兔子和编号在 [-10^9,10^9] 范围内的 2\times 10^9+1 个“物品”，第 i 只兔子可以选择两个物品 x_i - r_i 与 x_i + r_i 之一。每只兔子必须选一个物品，每个物品至多被一只兔子选中。求最多有多少只兔子能选中不同的物品（即不同的坐标）。

首先考虑一种简单情形：若某个物品只被一只兔子选中，那么最优方案显然是让这只兔子取走该物品。此时，这只兔子的另一个可选物品便可以被释放出来，可能让给其它兔子。

如果直接模拟这一过程，每次可能只能确定一只兔子的选择，最坏情况需要 O(n^2) 次操作。
为了避免重复遍历，我们可以用 DFS 来处理：当确定一只兔子选择某个唯一物品后，它释放出的另一个物品可能又成为其它兔子的唯一选择，这个过程可以递归进行。

完成上述唯一物品分配后，剩下的每个物品至少被两只兔子选中。可以证明，此时剩下的所有物品都能被兔子选中。

证明（反证法）：
假设存在某个物品最终无法被选中。由于兔子数量不超过物品数量（每只兔子选一个），若出现空缺，则必然存在重复选择。我们可以通过交换的方式，将空缺逐步调整到重复选择的位置，从而消除空缺，这与假设矛盾。因此，不存在无法被选中的物品。 \textbf{证毕} 。

于是，最终答案 = （通过唯一物品确定的兔子数量）+（剩余被兔子选过的物品数量）。

代码

时间复杂度 O(n)（忽略 unordered_map 的常数）。 

#include <bits/stdc++.h>
#define int long long
using namespace std;

unordered_map<int, unordered_set<int>> um; // 物品 -> 可选的兔子集合
vector<pair<int, int>> x;                 // 每只兔子的两个选择
unordered_set<int> us;                    // 剩余被选过的物品
vector<bool> vis;                         // 兔子是否还未确定
int n, ans = 0;

void DFS(int u) {
    if (um[x[u].first].size() == 1) {    // 第一个选择是唯一物品
        um.erase(x[u].first);             // 该物品被确定
        um[x[u].second].erase(u);         // 从第二个选择中移除该兔子
        vis[u] = false;                   // 标记该兔子已确定
        ans++;                            // 确定兔子数 +1
        if (um[x[u].second].size() == 1) {
            DFS(*um[x[u].second].begin()); // 第二个选择变为唯一物品，递归处理
        }
    } else if (um[x[u].second].size() == 1) {
        swap(x[u].first, x[u].second);    // 保证先判断唯一物品
        DFS(u);
    }
    return;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    x.resize(n + 1);
    vis.resize(n + 1, true);
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        x[i] = {a - b, a + b};
        um[a - b].insert(i);
        um[a + b].insert(i);
    }

    // DFS 处理所有唯一物品
    for (int i = 1; i <= n; i++) {
        if (vis[i]) {
            DFS(i);
        }
    }

    // 统计剩余被选过的物品
    for (int i = 1; i <= n; i++) {
        if (vis[i]) {
            us.insert(x[i].first);
            us.insert(x[i].second);
        }
    }

    cout << ans + us.size() << "\n";
    return 0;
}

本文使用 deepseek 润色。