HDU 1029 Ignatius and the Princess IV
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1029
题目翻译
给一个长度为奇数的序列，求一个在序列中出现(n + 1) / 2次的数字。
题解
智力题
如果一个数字出现的(n + 1) / 2次，那么他出现的次数可以抵消其他所有数
所以，我们记录一个Num , Cnt .
如果下一个数是Num则Cnt ++否则Cnt–（如果Cnt==0，那么Num更新成这个数，Cnt=1）
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include<cstdio> using namespace std; int n; int num,cnt; inline void solve() { scanf("%d", &num); cnt = 1; for (int i = 2; i <= n; i++){ int x; scanf("%d", &x); if (x != num) { cnt--; if (cnt == 0) { num = x; cnt = 1; } } else { cnt++; } } printf("%d\n", num); } int main() { while(scanf("%d", &n) != EOF) solve(); return 0; } |
原文链接：HDU 1029 Ignatius and the Princess IV
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!