题解 P1407 【工资】

Excim · 2017-06-29 21:36:37 · 题解

这题给的空间比较小，但实际上我们其实不需要那么多的变量

a[0]表示现在找到的最多的数,a[1]表示最多的数的数目

主要思路：如果读入的数与现有的最多的数不相等，那么就相互抵消，因为最多的数个数超过一半，所以经过所有的抵消之后，仍会有剩余，此时该数就存在a[0]中

其余解释见代码中的注释吧

#include<cstdio>
int n,i,t,a[2],x;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        a[0]=-1;//初始化为-1，非常重要，因为有输入数据为0的时候（样例第一组）
        a[1]=0;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d",&x);
            if(x==a[0])//如果与现有最多的数相等，则继续增加最多数的数目，为抵消其他数做准备 
            {
                a[1]++;
                continue;
            }
            if(a[0]==-1)//如果还没有找到最多的数，那么就将现在找到的数当做最多的数记录下来 
            {
                a[0]=x;
                a[1]=1;
                continue;
            }
            if(x!=a[0]&&a[1]>0)//如果当前已有一个最多的数，又不与刚输入的数不等，则两个数相互抵消 
            {
                a[1]--;
                if(a[1]==0) a[0]=-1;//如果抵消后之前最多的数个数变为0，则可视作前面所有的寻找无效，初始化重新开始 ，此操作并不会影响结果，经过抵消之后，最多数的数量在剩余数字中仍是最多的
                continue;
            }
        }
        printf("%d\n",a[0]);//最后输出找到的数即可，数据以保证最多的数个数超过一半 
    }
    return 0;
}