9639 . 综合题 Puls

完善程序(2)(精明与糊涂)

有N 个人,分为两类:i) 精明人:永远能正确判断其他人是精明还是糊涂;

ii) 糊涂人:判断不可靠,会给出随机的判断。已知精明人严格占据多数,即如果精明人有k 个,则满足 k>N/2。

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

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

例如,假设有三个人0、1、2。如果0说1是糊涂人,而1也说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;
}
38 . (单选题)

①处应填

39 . (单选题)

②处应填

40 . (单选题)

③处应填

41 . (单选题)

④处应填

42 . (单选题)

⑤处应填