C语言 · 色盲的民主

算法提高色盲的民主

时间限制：1.0s 内存限制：256.0MB

问题描述

　　n个色盲聚在一起，讨论一块布的颜色。尽管都是色盲，却盲得各不相同。每个人都有自己的主张，争论不休。最终，他们决定采取民主投票的方式决定布的颜色，不管布同不同意。某种颜色用字符串表示(字符串为颜色单词或词组，也就是可能有被空格隔开的两个单词组成的颜色词组)，只要字符串不同，程序即判断颜色不同。现在给出这n个人所选择的颜色，输出最有可能的颜色（也就是获得投票最多的颜色），如果有多个颜色获得了最多的投票，则将它们按字典序分行全部输出。

输入格式

　　第一行一个正整数n，表示色盲的人数
　　接下来n行，每行一句话

输出格式

　　若干行，获得投票最多的颜色，按字典序输出

样例输入

5
red
blue
black
black
blue

样例输出

black
blue

数据规模和约定

　　n<=1000
　　颜色单词最多20个字符，只包含小写字母或者空格

注

　　对于char s[20]，由于cin >> s是读取到空格处便会结束，也就是对于light red，用cin只能输入light。如果要整个输入一行，则使用cin.getline(s, 20)，其中20为这一行的最大长度，也就是你的s的容量，如果容量为30,则cin.getline(s, 30)。
　　另外，你在cin>>n以后cin.getline(s,30)应该会得到一个空字符串，这是因为整数n后面的换行符还未被输入。

作者注释：当看到“字典排序”，就想到用结构体，用qsort来做，还是掌握的不牢固，在大牛的指导下结合之前做过的题完成了代码。思路和细节看代码注释。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 #include<stdlib.h>
 5 #include<ctype.h>
 6 /*定义一个结构体:包括定义颜色的名称及其个数*/
 7 typedef struct Color{
 8     char color[50];//不同的颜色 
 9     int num;//每个颜色的个数 
10 }col;
11 int cmp(const void *a,const void *b){
12     col c = *(col*)a;
13     col d = *(col*)b;
14     //按数量的多少对颜色名称进行字典排序 
15     if(c.num == d.num){
16         return strcmp(c.color,d.color);
17     }else{
18         return d.num - c.num;
19     }
20 }
21 int main(){
22     col co[1000];//定义结构体数组 
23     char color[20];//颜色单词最多20个字符
24     int re=0;//表需要排序的颜色个数,初值为0 
25     int n;//数据组数 
26     scanf("%d",&n);
27     for(int i=0;i<n;i++){
28         int j=0;//下标 
29         //输入一个颜色单词
30         scanf("%s",&color); 
31         //先判断有没有存着此颜色
32         for(j=0;j<re;j++){
33             if(strcmp(color,co[j].color)==0)
34                 break;
35         }
36         //若已经存了，该颜色数量+1 
37         if(re!=j){
38             co[j].num++;
39         }
40         //若没有存，此时存进去 
41         else{
42             strcpy(co[re].color,color);
43             co[re].num=1;//改颜色的数量为1
44             re++;//需要排序的颜色个数+1 
45         }
46     }
47     //排序 
48     qsort(co,re,sizeof(co[0]),cmp);
49     for(int i=0;i<n;i++){ 
50         if(co[i].num == co[0].num){
51             printf("%s
",co[i].color);
52         }
53     }
54     return 0;
55 }

上述过程在思路上没有问题，但是对于本题提交是不通过的——错在数据的处理的细节上。

%s：格式化字符串,不能接收回车换行空格符；

gets()：用于从读入一个整行，以' '或EOF结束；

getchar()：用于读入一个字符，并返回这个字符.

对于本题：输入n后有一个换行，而且每个颜色后都有一个换行，因此要注意用getchar()来接收换行，用gets()，接收数据。

 1 /*
 2     注意：%s不能接收空格、回车；
 3     getchar()可以消除回车、空格符；
 4     gets()一般与getchar()配合使用。 
 5 */ 
 6 #include<stdio.h>
 7 #include<string.h>
 8 #include<math.h>
 9 #include<stdlib.h>
10 #include<ctype.h>
11 /*定义一个结构体:包括定义颜色的名称及其个数*/
12 typedef struct Color{
13     char color[50];//不同的颜色 
14     int num;//每个颜色的个数 
15 }col;
16 int cmp(const void *a,const void *b){
17     col c = *(col*)a;
18     col d = *(col*)b;
19     //按数量的多少对颜色名称进行字典排序 
20     if(c.num == d.num){
21         return strcmp(c.color,d.color);
22     }else{
23         return d.num - c.num;
24     }
25 }
26 int main(){
27     col co[2000];//定义结构体数组 
28     char color[30];//颜色单词最多20个字符
29     int re=0;//表需要排序的颜色个数,初值为0 
30     int n;//数据组数 
31     scanf("%d",&n);
32     getchar();//输入n后有一个回车，用getchar()处理掉 
33     for(int i=0;i<n;i++){
34         int j=0;//下标 
35         //输入一个颜色单词
36 //        scanf("%s",&color); 
37         gets(color);//%s不能处理回车换行空格符,而此题每个数据都有一个换行,用gets接收 
38         //先判断有没有存着此颜色
39         for(j=0;j<re;j++){
40             if(strcmp(color,co[j].color)==0)
41                 break;
42         }
43         //若已经存了，该颜色数量+1 
44         if(re!=j){
45             co[j].num++;
46         }
47         //若没有存，此时存进去 
48         else{
49             strcpy(co[re].color,color);
50             co[re].num=1;//改颜色的数量为1
51             re++;//需要排序的颜色个数+1 
52         }
53     }
54     //排序 
55     qsort(co,re,sizeof(co[0]),cmp);
56     for(int i=0;i<n;i++){ 
57         if(co[i].num == co[0].num){
58             printf("%s
",co[i].color);
59         }
60     }
61     return 0;
62 }