杭州电子科技大学Online Judge 之 “漂浮的气球（ID1004）”解题报告

巧若拙（欢迎转载，但请注明出处：http://blog.csdn.net/qiaoruozhuo）

题目描述：

Let the Balloon Rise

Problem Description

Contest time again! How excited it is tosee balloons floating around. But to tell you a secret, the judges‘ favoritetime is guessing the most popular problem. When the contest is over, they willcount the balloons of each color and find the result.

This year, they decide to leave this lovelyjob to you.

Input

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

A test case with N = 0 terminates the inputand this test case is not to be processed.

Output

For each case, print the color of balloonfor the most popular problem on a single line. It is guaranteed that there is aunique solution for each test case.

Sample Input

5

green

red

blue

red

red

3

pink

orange

pink

0

Sample Output

red

pink

Author

WU, Jiazhi

Source

ZJCPC2004

题目分析：

蹩脚的翻译：

漂浮的气球

比赛又开始了！最刺激的莫过于看着气球徐徐升起。告诉你一个秘密，法官们最乐于猜测哪种颜色的气球最受欢迎。当比赛结束时，他们要计算每种颜色的气球数量，并选出数量最多的气球颜色。今年，他们打算把这有趣的工作交给你。

输入

输入包含多组测试数据。每个测试用例开始于一个整型数N（0<N<=1000）——气球的总数。接下来的N行输出每个气球的颜色，气球的颜色用不多于15个小写字母的字符串表示。

测试用例用N =0结束输入，且该测试例不被处理。

输出

对于每一组测试数据，输出最热门的气球颜色。确保每一组测试数据都能得到解决。

算法分析：

本题算法很简单，就是一个读入字符串和比较大小的基本应用。数据结构是一个包含了气球颜色和数量的结构体。为了简化代码和提高速度，我把存储了气球信息的结构体数组设置为全局变量。

为了提高查找的效率，我把数组按照颜色字符串大小增序排列，采用折半查找的方法。先找到插入位置，如果是已有颜色气球，只需增加该色气球的数量，否则插入新的结点。最后遍历数组找出数量最多的气球，并输出其颜色。

程序的亮点在于折半插入算法，这也是最容易出错的地方。

说明： 

算法思想：查找和插入。

数据结构：包含一个字符串和一个整型数据的结构数组。

时间复杂度：O(Nloglen);其中N为气球数量，len为气球颜色总数

空间复杂度：O(N);

代码如下：

#include<stdio.h>

#include<stdlib.h>

#define MAX 1010

struct Node{

   char col[16];//气球颜色

   int num;//气球数量

} ball[MAX];

int GetMax(int n);

int Insert(char *str, int n);//折半插入新结点

int main(void)

{

       charstr[16];

       inti, len, n, pos;

       scanf("%d",&n);

   while (n != 0)

    {

       len = 0; //数组长度归零

       for (i=0; i<n; i++)

       {

           scanf("%s", str);

           len = Insert(str, len);//插入新结点，并返回数组长度

       }

       pos = GetMax(len); //返回数量最多的气球序号

       puts(ball[pos].col);

       scanf("%d", &n);

    }

   return 0;

}

int GetMax(int n)//查找数量最多的气球序号

{

   int i, max = 0;

   for (i=0; i<n; i++)

    {

       if (ball[i].num > ball[max].num)

           max = i;

    }

   return max;

}

int Insert(char *str, int n)//折半插入新结点

{

   int i, flag = 0;//标记是否为已有颜色结点

   int mid, low = 0, high = n - 1;

   if (n == 0)

    {

       strcpy(ball[0].col, str);

       ball[0].num = 1;

       return 1;

    }

   while (low <= high)//折半查找插入位置

    {

       mid = (low + high)/2;

       if (strcmp(str, ball[mid].col) == 0)

       {

              flag = 1;

                     break;

       }    

       else if (strcmp(str,ball[mid].col) < 0)

           high = mid - 1;

       else

           low = mid + 1;

    }

   if (flag == 1) //增加已有颜色气球数量

           ball[mid].num++;

   else //插入新结点

    {

       for (i=n; i>low; i--)

           ball[i] = ball[i-1];   

       strcpy(ball[low].col, str);

       ball[low].num = 1;

       n++;   

    }

   return n; //返回新的数组长度

}

杭州电子科技大学Online Judge 之 “漂浮的气球（ID1004）”解题报告