CSP-J 2025 第一轮 第 40 题：精明与糊涂：③处应填

题目

（2）（精明与糊涂）有 $N$ 个人，分为两类：
i) 精明人：永远能正确判断其他人是精明还是糊涂；
ii)糊涂人：判断不可靠，会给出随机的判断。

已知精明人严格占据多数，即如果精明人有 $k$ 个，则满足 $k > N/2$。

你只能通过函数 $\text{query}(i, j)$ 让第 $i$ 个人判断第 $j$ 个人：返回 $\text{true}$ 表示判断结果为“精明人”；返回 $\text{false}$ 表示判断结果为“糊涂人”。你的目标是，通过这些互相判断，找出至少一个百分之百确定的精明人。同时，你无需关心 $\text{query}(i, j)$ 的内部实现。

以下程序利用“精明人占多数”的优势。设想一个“消除”的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选人必然属于多数派，即精明人。

例如，假设有三人 $0, 1, 2$。如果 $0$ 说 $1$ 是糊涂人，而 $1$ 也说 $0$ 是糊涂人，则 $0$ 和 $1$ 至少有一个是糊涂人。程序将同时淘汰 $0$ 和 $1$。由于三人里至少有两个精明人，我们确定 $2$ 是精明人。

试补全程序。

#include <iostream>
#include <vector>
using namespace std;

int N;
bool query(int i, int j);

int main() {
    cin >> N;

    int candidate = 0;
    int count = ①;
    for (int i = 1; i < N; ++i) {
        if (②) {
            candidate = i;
            count = 1;
        } else {
            if (③) {
                ④;
            } else {
            count++;
            }
        }
    }
    cout << ⑤ << endl;
    return 0;
}

③处应填（ ）

选项

• A. query(candidate, i) == false
• B. query(i, candidate) == true
• C. query(candidate, i) == false && query(i, candidate) == false
• D. query(candidate, i) == false || query(i, candidate) == false

答案

D

题解

答案是 D：

``cpp query(candidate, i) == false || query(i, candidate) == false ``

关键是：一精明、一糊涂的两个人，一定要抵消。

两人互相判断时：

• 都是精明人：双方必然都返回 true。
• 一精明、一糊涂：精明人一定会判断对方为糊涂，所以至少一方返回 false。
• 都是糊涂人：任何结果都有可能。

因此，只要至少一方返回 false，就可以抵消这两个人。这时被删除的要么是一精明、一糊涂，要么是两个糊涂人，精明人仍然严格占多数。

反过来，如果双方都返回 true，两人必然属于同一类，可以用 count++ 累积。count 表示当前尚未抵消、与候选人同类的人数；抵消时执行 count--，归零后再换候选人。最终留下的候选人必然是精明人。

为什么 C 不行？ 假设三个人依次为“糊涂、精明、精明”，第一个糊涂人一直说别人精明。后两人虽然都说候选人糊涂，但双方不会同时返回 false，C 就一直不抵消，最后错误地留下糊涂人。A 在这个例子中也会失败。

完整填空为：

``cpp ① 1 ② count == 0 ③ !query(candidate, i) || !query(i, candidate) ④ count-- ⑤ candidate ``