#1382. [CSP2025 入门级] 第 42 题
[CSP2025 入门级] 第 42 题
()(精明与糊涂)有 个人,分为两类:
i) 精明人:永远能正确判断其他人是精明还是糊涂;
ii)糊涂人:判断不可靠,会给出随机的判断。
已知精明人严格占据多数,即如果精明人有 个,则满足 。
你只能通过函数 让第 个人判断第 个人:返回 表示判断结果为“精明人”;返回 表示判断结果为“糊涂人”。你的目标是,通过这些互相判断,找出至少一个百分之百确定的精明人。同时,你无需关心 的内部实现。
以下程序利用“精明人占多数”的优势。设想一个“消除”的过程,让人们互相判断并进行抵消。经过若干轮抵消后,最终留下的候选人必然属于多数派,即精明人。
例如,假设有三人 。如果 说 是糊涂人,而 也说 是糊涂人,则 和 至少有一个是糊涂人。程序将同时淘汰 和 。由于三人里至少有两个精明人,我们确定 是精明人。
试补全程序。
#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. count--
B. break
C. count++
D. candidate = i
{{ select(1) }}
count--breakcount++candidate = i