活动投票 题目描述 时限: 0.5s 内存: 2M 衡中活动很多,人也很多,一次活动有 n 个学生参与投票,现已知一名参赛选手票数超过半数,求其参赛号 a_i (参赛号随机, 0le a_i le 2147483647 ) 。 输入格式 第一行一个整数 n 。 第二行 n 个整数 N_i 代表第 i 个学生所投选手的参赛号。 输出格式 超过半数选手的参赛号。 样例 样例输入 10 5 1 2 5 5 2 3 5 5 5 样例输出 5 数据范围与提示 100\% 的数据满足: n ≤3000000 ; 题解 数组,肯定不行,直接炸,只能通过其他方法求解。 那么只能用思维来做了,我用的方法是只求已知数列中的半数, 如果前面的数和他不同,那么就cnt--,直到为0时他肯定没超过半数,就相当于抵消了, 如果前面的数与他相同,那么cnt++,计算个数, 如果cnt==0,那么说明此时前面没有超过半数的数字, 最后出来的就是超过半数的数字。 code #include <cstdio> int ans, cnt, x, y; int main() { scanf("%d", &x); while (x--) { scanf("%d", &y); if (cnt == 0) ans = y, cnt++; else if (ans == y) cnt++; else cnt--; } printf("%d", ans); }