PAT-1054 The Diamond Color


		题目描述：
Behind the scenes in the computer's memory, color is always talked about as a series of 24 bits of information for each pixel. In an image, the color with the largest proportional area is called the dominant color. A strictly dominant color takes more than half of the total area. Now given an image of resolution M by N (for example, 800x600), you are supposed to point out the strictly dominant color.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive numbers: M (<=800) and N (<=600) which are the resolutions of the image. Then N lines follow, each contains M digital colors in the range [0, 224). It is guaranteed that the strictly dominant color exists for each input image. All the numbers in a line are separated by a space.
Output Specification:
For each test case, simply print the dominant color in a line.
Sample Input:
5 3
0 0 255 16777215 24
24 24 0 0 24
24 0 24 24 24
Sample Output:
24
 
普通的思路:标记每一个数出现的次数，结果会超时，有一组数据过不去。
[cpp 
#include<iostream>  
using namespace std;  
  
#define max 170000000  
int input[max];  
long t,temp;  
int main()  
{  
    int M,N;  
    int count = 0;  
    int i,j;  
    cin>>M>>N;  
   
    //采用以下for循环会超时  
    for(j=0; j<M*N; j++)  
    {  
        cin>>t;  
        input[t]++;  
        if(input[t] > count) {count = input[t]; temp = t;}  
    }  
   
    cout<<temp<<endl;     
    return 0;  
}  
 
正确解法一：采用map。
代码来自于：http://blog.csdn.net/matrix_reloaded/article/details/8818628
[cpp]  
#pragma warning (disable:4786)  
#include<iostream>  
#include<string>  
#include<cstdio>  
#include<map>  
using namespace std;  
  
int main()  
{  
    int m,n;  
    while(scanf("%d%d",&m,&n)!=EOF)  
    {  
        int i,j;  
        string s;  
        map<string,int> ans;  
          
        map<string,int>::iterator p;  
  
        char ss[10000];  
  
        for(i=0;i<n;i++)  
        {  
            for(j=0;j<m;j++)  
            {  
                scanf("%s",ss);  
                s=ss;  
                ans[s]++;  
            }  
        }  
        int cnt=-1;  
        for(p=ans.begin();p!=ans.end();p++)  
        {  
            if(p->second>cnt)  
            {  
                s=p->first;  
                cnt=p->second;  
            }  
        }  
        printf("%s\n",s.c_str());  
    }  
    return 0;  
}  
正确解法二：因为我们所要求的数出现的次数超过总数目一半，所以将不相同的数两两抵消，那么最终剩下的便是我们要求的数。
代码来自于：http://blog.csdn.net/jjike/article/details/8970540
[cpp] 
#include<iostream>  
using namespace std;  
  
const int MAXN = 10000;  
int img[MAXN]={0};  
  
int main()  
{  
    int m,n,mn;  
    int i,j,x;  
    freopen("C:\\Documents and Settings\\Administrator\\桌面\\input.txt","r",stdin);  
  
    bool fg = false;  
    //cin>>m>>n;  
    scanf("%d%d",&m,&n);  
    mn = m * n;  
    for(i = 0; i < mn; i++){       
        //cin>>img[i];  
        scanf("%d",&img[i]);          
    }  
    int cad, nTime=0;  
    for(i = 0; i < mn; i++){  
        if(nTime == 0){  
            cad = img[i];  
            nTime = 1;  
        } else {  
            if(cad == img[i])  
                nTime++;  
            else   
                nTime--;              
        }  
    }  
    //cout<<cad;  
    printf("%d",cad);  
    return 0;  
}

补充：软件开发 , C++ ,