题解 P1407 【工资】

Makasukaka · 2017-10-26 16:12:08 · 题解

运用抵消的思想

记录下当前的存储的数ans

和它出现的次数tot

如果新输入的数不等于ans

就抵消一次

直到tot等于0时

说明当前的ans一定不会保留到最后..

这会保证众数一定会保留到最后

因为没有足够的数能够把众数抵消完。。

具体思想还需要各位自己领悟

思想也比较精巧

想通了你会恍然大悟的。。

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        int tot=0,n,ans=0;
        scanf("%d",&n);
        for(int j=1;j<=n;j++){
            int t;
            scanf("%d",&t);
            if(ans!=t){//如果当前的数不等
                if(tot==0)ans=t;//如果没有机会了 替换
                else tot--;//消耗一次机会
            }
            else tot++;//机会+1
        }
        printf("%d\n",ans);//输出答案
    }
    return 0;
}