杭电ACM 1004：Let the Ballon Raise-白红宇

杭电ACM 1004：Let the Ballon Raise

阅读量：2255 次

发布时间：2019-05-09

本文共 2750 字，大约阅读时间需要 9 分钟。

杭电刷题第五篇。原创作品转载请注明出处

原题回顾

Problem Description

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.

Input

Input 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

Output

For 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

其实这道题按常规来说算是简单题，在这一道题上我用了两种方法，刚开始第一种我直接联想到了用到C++的容器进行，对C++比较熟悉的同学应该很容易想到这个，C++的容器很强大，对类似的问题很简单的代码就能搞定，下面是我用c++的map和vector容器写出的代码，并且AC。

方法一：

#include 
   
    #include
    
     #include
     
      #include
      #include
       
        #include
        
         using namespace std;typedef pair
         
           PAIR;//定义排序比较函数，通过value比较bool cmp_by_value(const PAIR& lhs, const PAIR& rhs) { return lhs.second > rhs.second; }int main(void){ int n; map
          
           color_balloon; string * input_str; while(cin>>n&&n) { input_str=new string[n];//为输入的颜色分配空间 for(int i=0;i
           
            >input_str[i]; ++color_balloon[input_str[i]];//提取input_str[]计数器并对其加1 } //把map中元素转存到vector中 vector 
            
              color_str_vec(color_balloon.begin(),color_balloon.end()); //按降序排序 sort(color_str_vec.begin(),color_str_vec.end(),cmp_by_value); //color_str_vec已经按照降序排序，输出第一个即为出现次数最多的一个 cout<
             
              <

上面的过程如果对C++不是很熟悉的话可能比较难理解，有关C++的map和vector容器使用方法可以查看我本博客的《c/c++应用》两篇文章,，里面有介绍。自己可以进行查阅。在这里我就不再一一介绍。下面我们就来看我不使用容器来写的另一个代码，也被AC了，见下面。

方法二：

#include 
   
    #include
    
     #include
     
      using namespace std;//定义一个结构体来存储颜色和颜色数struct ballon{    string color;    int num;};int main(void){    int n,Max_color,Max_i;    ballon *input_ballon;    string str="null";    while(cin>>n&&n)    {        input_ballon=new ballon[n];        //输入的颜色存入到结构体中，并且都给自己颜色数赋值为1，方便后面累加        for(int i=0; i
      
       >input_ballon[i].color;            input_ballon[i].num=1;        }        /*        思路：最直接的方法，依次比较两个字符串是否相等，相等的话保留第一个，并且num+1；        再将比较的第二个字符串赋值为“null”,下次比较的时候遇到字符串null就跳过去。直到累加结束        */        for(int j=0; j
       
        Max_color)            {                Max_color=input_ballon[k].num;                Max_i=k;            }        }        //输出        cout<
        
         <

这一段代码有点长，也使用了最简单易懂的方法算出，整个代码的难点及其思路我已经在代码中标注。希望这两篇代码会给你点启发，你也可以用自己更加简便的方法。有需要探讨的，请给我留言。

你可能感兴趣的文章