HDOJ 1029 Ignatius and the Princess IV 【数论】

HDOJ 1029 Ignatius and the Princess IV 【math】

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1029

---

N是奇数，并且最后的special integer出现次数至少为 (N+1)/2
所以special integer出现的次数一定比其他所有数出现的总数还多
一点一点滴 耗死其他的数就可以鸟。。。

---

#include<cstdio>
int N, num, cnt, ans;

int main(){
    while(~scanf("%d", &N)){
        cnt = 0;
        while(N--){
            scanf("%d", &num);
            if(cnt == 0){ // 刚开始或一个数已经被耗尽 开始计算新的数据
                ans = num;
                cnt++;
            }
            else{
                if(ans == num) cnt++;
                else cnt--;
            }
        }
        printf("%d
", ans);
    }
    return 0;
}

版权声明：本文为博主原创文章，未经博主允许不得转载。