STL-map-A

A - Let the Balloon Rise

Contest time again! How excited it is to see balloons floating around. But to tell you a secret, the judges' favorite time is guessing the most popular problem. When the contest is over, they will count the balloons of each color and find the result.

This year, they decide to leave this lovely job to you.

InputInput contains multiple test cases. Each test case starts with a number N (0 < N <= 1000) -- the total number of balloons distributed. The next N lines contain one color each. The color of a balloon is a string of up to 15 lower-case letters.

A test case with N = 0 terminates the input and this test case is not to be processed.
OutputFor each case, print the color of balloon for the most popular problem on a single line. It is guaranteed that there is a unique solution for each test case.
Sample Input

5
green
red
blue
red
red
3
pink
orange
pink
0

Sample Output

red
pink

　　题目大意：给出n种颜色，要你统计出期中出现次数最多的颜色
　　代码一：最原始的办法解决，用双重for循环，每次输入一种颜色都进行一次循环，判断该颜色是否出现过，复杂度O(n

²

).

#include<iostream>
#include<string> 
using namespace std;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0)    break;
        
        string str[1010];
        cin.get();//！！！！！ 
        for(int i=0;i<n;i++)
            getline(cin,str[i]);
            
        int num[1010];
        int max = 0;
        for(int i=0;i<n;i++){
            num[i] = 1;
            for(int j=i+1;j<n;j++){
                if(str[i]==str[j])
                    num[i]++;
            }
            if(num[i]>num[max])    max = i;
        }
        cout << str[max] << endl;
    }
}

 　　代码二：使用STL里的map容器

#include<bits/stdc++.h>
using namespace std;

int n;
map<string, int>ballon;

int main(){
    while(~scanf("%d", &n) && n){
        ballon.clear();
                cin.get();
        for(int i=0; i<n; i++){
            string colors;
            getline(cin, colors);
            if(ballon.find(colors) != ballon.end())//该颜色已经出现过
                ballon[colors] ++;
            else
                ballon.insert(map<string, int>::value_type(colors, 1)); 
        }
        int max = 0;
        string color;
        map<string, int>::iterator it;
        for(it = ballon.begin(); it != ballon.end(); it++){
            if(it->second > max){
                max = it->second;
                color = it->first;
            }
        }
        cout << color << endl;
    }
} 

　　代码三：是上段代码的修改，发现无需判断颜色是否出现过，直接插入即可

#include<iostream>
#include<map>
#include<string>
#include<algorithm>
using namespace std;

int main(){
    int n;
    while(~scanf("%d", &n) && n){
        map<string,int>ballon;
        string colors;
        for(int i=0; i<n; i++){
            cin >> colors;    //用getline(cin,colors)就WA了，这谁能解释 
            ballon[colors]++;
        }
        int max = 0;
        string color;
        map<string,int>::iterator it;
        for(it=ballon.begin(); it!=ballon.end(); it++){
            if(max < it->second){
                max = it->second;
                color = it->first;
            }
        }
        cout << color << endl;
    }
}

　　（1）类似题目，要统计某种东西的出现次数时，就可以使用map容器来做，简单又快。

　　（2）有个点，在一开始输入气球的颜色时，用cin >> colors就没有问题，而用getline(cin, colors)时就WA了，而解决的办法是在输入n之后，加一个cin.get()，我真的还解释不通这个东西，反正既然colors已经是用string定义的了，就没必要getline了，直接cin即可。

　　（3）map的迭代器种，it->first即指的<>种的第一个，second就是第二各咯。

　　（4）map的插入ballon.insert(map<string, int>::value_type(colors, 1))，括号里的格式要记住，当然map可能有去重的功能，不需要判断颜色是否出现过，直接ballon[colors]++即可。

　　STL的功能很强大，却还很陌生，要多加积累。