精明与糊涂(多数派候选消除)有N个人,分为两类:
①精明人:永远能正确判断其他人是精明还是糊涂;
②糊涂人:判断不可靠,会给出随机的判断。
已知精明人严格占据多数,即如果精明人有k个,则满足(k>N/2)。你只能通过函数query(i,j)让第i个人判断第j个人:返回true表示判断结果为“精明人”;返回false表示判断结果为“糊涂人”。目标是通过互相判断,找出至少一个百分之百能确定的精明人(无需关心query(i,j)的内部实现)。以下程序利用“精明人占多数”的优势,通过“消除”过程让人们互相判断并抵消,经过若干轮抵消后,最终留下的候选者必然属于多数派(精明人),试补全程序。③处应填()
#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;
}query(candidate,i)==false
query(i,candidate)==true
query(candidate,i)==false && query(i,candidate)==false
query(candidate,i)==false || query(i,candidate)==false