csppass
连续 00 XP登录 / 注册
202539完善程序贪心算法提高

精明与糊涂:①处应填

题目

完善程序:精明与糊涂。有 N 个人,精明人永远能正确判断他人,糊涂人的判断不可靠;已知精明人严格占多数。只能通过 query(i,j) 让第 i 个人判断第 j 个人。以下程序用多数投票法的抵消思想找出一个必然是精明人的候选者,请补全程序。 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 { ③ { ④; } else { count++; } } } cout << ⑤ << endl; } ①处应填( )

考点拆解
Boyer-Moore 多数投票算法的思想:不断抵消,最终留下的候选者必属于多数派
把经典多数投票算法改写成需要双向验证的查询形式
易错提醒
阅读程序题要按变量变化顺序手推,不要跳步
选择题要检查单位、边界和题目中的否定词