70020 - 2025CSP-J 完善程序2
统计题目(材料题)
(2)精明与糊涂
有N个人，分为两类：
① 精明人:永远能正确判断其他人是精明还是糊涂;
② 糊涂人:判断不可靠，会给出随机的判断。
已知精明人严格占据多数，即如果精明人有$k$个，则满足$k>N/2$。你只能通过函数query(i,j)让第$i$个人判断第$j$个人:返回true表示判断结果为“精明人”;返回false表示判断结果为“糊涂人"。目标是通过互相判断，找出至少一个百分之百能确定的精明人(无需关心query(i，j)的内部实现)。
以下程序利用”精明人占多数”的优势，通过“消除”过程让人们互相判断并抵消，经过若干轮抵消后，最终留下的候选者必然属于多数派(精明人)，试补全程序。
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4 int N;
5 bool query(int i, int j);
6
7 int main() {
8 cin >> N;
9 int candidate = 0;
10 int count = ①;
11 for (int i = 1; i < N; ++i) {
12 if ( ②) {
13 candidate = i;
14 count = 1;
15 } else {
16 ③ {
17 ④;
18 } else {
19 count++;
20 }
21 }
22 }
23 cout << ⑤ << endl;
24 return 0;
25 }
关注我们
