1054 The Dominant Color (20 分)

水~。

map<int,int> mp;
int n,m;

int main()
{
    cin>>m>>n;

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            int color;
            cin>>color;
            mp[color]++;
        }

    for(auto t:mp)
    {
        if(t.se > n*m/2)
        {
            cout<<t.fi<<endl;
            break;
        }
    }
    //system("pause");
    return 0;
}

本题如果不用map，那么可以采用这样的思路解决：由于题目要求必须超过半数，因此有超过半数的数相同的，如果采用两两不相同的数相互抵消的做法，最后一定会剩下那个超过半数的数字。于是可以设置一个变量ans存放答案，设置另一个变量count计数ans出现的次数，然后在读入时判断ans与读入的数字是否相等，如果不相等，则令其抵消一次ans(即令count)；如果相等，则令count加1。当然，如果某步count被抵消至0，则令新的数字为ans。这样最后剩下来的数字一定是所求数字。