Compatible Pairs

题目描述

在偏远的乡村深处，农夫 John 的奶牛并不是普通的农场动物——它们是一个秘密的奶牛情报网络的一部分。每头牛都携带一个由精英奶牛密码学家精心分配的 ID 编号。然而，由于农夫 John 相当随意的打标系统，一些奶牛最终拥有了相同的 ID。 农夫 John 记录到共有 $N$（$1\le N\le 2\cdot 10^5$）个不同的 ID 数字；对于每个不同的 ID $d_i$（$0\le d_i\le 10^9$），有 $n_i$（$1\le n_i\le 10^9$）头奶牛共享该 ID。 奶牛只能两两交流，并且它们的秘密加密方法有一条严格规则：两头牛只有在它们不是同一头牛，且它们的 ID 之和等于 $A$ 或 $B$（$0\le A\le B\le 2\cdot 10^9$）时，才能交换信息。一头牛同一时间只能参与一次交流（即任何奶牛不能属于多个配对）。 农夫 John 希望最大化互不重叠的交流配对数量，以确保最佳的信息流。你能确定同时最多可以进行多少次交流吗？

输入格式

第一行包含 $N$、$A$、$B$。 接下来 $N$ 行每行包含 $n_i$ 和 $d_i$。任意两个 $d_i$ 都不相同。

输出格式

输出可以同时形成的、互不重叠的可交流配对的最大数量。 注意，本题涉及的整数可能很大，可能需要使用 64 位整数数据类型（例如 C/C++ 中的 "long long"）。

4 4 5
17 2
100 0
10 1
200 4

118

4 4 5
100 0
10 1
100 3
20 4

30

提示

ID 为 $0$ 的奶牛可以与 ID 为 $4$ 的奶牛交流，因为它们的 ID 之和为 $4$。由于共有 $100$ 头 ID 为 $0$ 的奶牛和 $200$ 头 ID 为 $4$ 的奶牛，因此这种 ID 组合最多可以形成 $100$ 对交流配对。 ID 为 $4$ 的奶牛也可以与 ID 为 $1$ 的奶牛交流（和为 $5$）。共有 $10$ 头 ID 为 $1$ 的奶牛，并且还剩下 $100$ 头未配对的 ID 为 $4$ 的奶牛，因此还能再形成 $10$ 对。 最后，ID 为 $2$ 的奶牛可以与另一头相同 ID 的奶牛交流。由于共有 $17$ 头 ID 为 $2$ 的奶牛，因此还能再形成 $8$ 对。 总计共有 $100+10+8=118$ 对交流配对。可以证明这是可能的最大配对数。

将 ID 为 $0$ 与 $4$ 配对可形成 $20$ 对，将 ID 为 $1$ 与 $3$ 配对可形成 $10$ 对。可以证明这是最优配对，总计得到 $30$ 对。

评分（SCORING）： 输入 3-4：$A=B$ 输入 5-7：$N\le 1000$ 输入 8-12：无额外限制 题目鸣谢：Benjamin Qi

标签: USACO|2025|Silver

来源

USACO|2025|Silver