（HDU）1004 -- Let the Balloon Rise（让气球飞）

问题描述
比赛时间到啦ヾ(ﾟ∀ﾟゞ)！ 看到气球漂浮起来是多么鸡冻激动的事情~ 但是告诉你一个秘密，评委们最喜欢猜测哪个问题最受欢迎。 当比赛结束后，他们会计算每种颜色的气球数量，并找到结果。今年，他们决定把这个可爱的工作交给你。

 

输入
输入包含多个测试用例。 每个测试用例以数字N（0 <N <= 1000）开始—— 表示气球的总数。 接下来的N行每行各包含一种颜色。 气球的颜色是最多含有15个小写字母的字符串。

当N测试用例为N=0表示终止输入，并且不会处理此测试用例。
 

输出
对于每种情况，在一行上输出最受欢迎问题的气球的颜色。 保证每个测试用例有唯一的解决方案。
 

样例输入

5
green
red
blue
red
red
3
pink
orange
pink
0

样例输出

red
pink

首先把n个输入颜色存入数组，再用一个对应数组表示这n个颜色处理值，需要遍历两遍。

假设第一次我们的数组得到的结果是这样的：

n	1	2	3	4	5	6
color	black	black	red	orange	orange	orange
num	0	0	0	0	0	0

第一个循环把color数组的字符串都输入好，

接下来第二个循环从第2个字符串开始，统计前面的字符串是否和它相同，相同一次则对应num+=1；

处理完了red的时候，表格是这样的：

n	1	2	3	4	5	6
color	black	black	red	orange	orange	orange
num	0	1	0	0	0	0

处理完最后一个orange，表格是这样的：

n	1	2	3	4	5	6
color	black	black	red	orange	orange	orange
num	0	1	0	0	1	2

 最后对这n个num进行统计，得出num的最大值位于n的哪个值处。

示例是n=6时num最大，输出对应的颜色orange，记得换行。

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int i,j,n,num[1000],max,t;
    char color[1000][16];
    while(scanf("%d",&n)!=EOF)
    {
        if(n)
        {
            num[0]=0;
            scanf("%s",color[0]);
            for(i=1;i<n;i++)
            {
                num[i]=0;
                scanf("%s",color[i]);
                for(j=0;j<=i-1;j++)
                {
                    if(strcmp(color[i],color[j])==0)
                        num[i]+=1;
                }
            }
            max=0;
            t=0;
            for(i=1;i<n;i++)
            {
                if(max<num[i])
                {
                    max=num[i];
                t=i;
                }
            }
            printf("%s
",color[t]);
        }
    }
    return 0;
}

代码改进一，用结构体，将num和color对应起来。

代码改进二，将每个num值初始化为1，这样最后得到的结果可以知道颜色最多出现了几次。

 

思考：如果这题最后需要将颜色按照出现次数由少到多输出，并且输出每个颜色出现的次数怎么办？

修改上述代码有点麻烦，于是换一种思考的方式。

同样需要两个数组color和num（或者结构体）来实现，

额外使用一个temp数组来缓存处理，一个kind的int变量来计算颜色种类。

1.声明时初始化所有num数组值为0，kind的值为0；

2.用strcpy函数将color[0]赋值为'null'；（头文件要有string）

3.经过上面的处理后，表格是这样的：（同样使用上面的例子）

kind	0
color	null	待处理	待处理	待处理	待处理	待处理	待处理
num	0	0	0	0	0	0	0

4.对于这n个气球，单个循环处理：
　　将气球颜色输入到temp，用strcmp函数判断temp字符串和已知的color[i]字符串是否相同。（i=0;i<=kind;i++）

　　如果相同——对应的num[i]+=1，直接跳出内循环，节省时间处理下一个气球；

　　如果不同——注意是在内循环结束之后，kind+=1；color[kind]=temp;num[kind]+=1;

之前的例子n=6 black black red orange orange orange

处理到1的时候表格是这样的：

kind	0	1
color	null	black	待处理	待处理	待处理	待处理	待处理
num	0	1	0	0	0	0	0

处理到2的时候表格是这样的：

kind	0	1
color	null	black	待处理	待处理	待处理	待处理	待处理
num	0	2	0	0	0	0	0

处理到3的时候表格是这样的：

kind	0	1	2
color	null	black	red	待处理	待处理	待处理	待处理
num	0	2	1	0	0	0	0

处理到6的时候表格是这样的：

kind	0	1	2	3
color	null	black	red	orange	待处理	待处理	待处理
num	0	2	1	3	0	0	0

5.每个数据处理完后，我们知道了颜色的种类有kind种，对应名字是color[kind]，对应数量是num[kind]。后面的处理可以省略了...

这道题保证了出现的次数不相同，可以修改一下，要求颜色出现次数相同的时候，按照字典序排列，其实也没差多少啦。