信奥赛一本通：数据排序（合影效果、病人排队、明明的随机数、单词排序、出现次数超过一半的数、统计字符数）

随机数、单词排序、出现次数超过一半的数、统计字符数）"/>

信奥赛一本通：数据排序（合影效果、病人排队、明明的随机数、单词排序、出现次数超过一半的数、统计字符数）

数据排序

• • 1182：合影效果
  • 1183：病人排队
  • 1184：明明的随机数
  • 1185：单词排序
  • 1186：出现次数超过一半的数
  • 1187：统计字符数

1182：合影效果

由题目可知，n个人有 性别与身高两种属性，则我们用结构体去做。

1. 定义结构体，并输入值。

struct Student{string sex;double high;
};
int main(){Student stu[105];int n;cin>>n;for(int i=0;i<n;i++){cin>>stu[i].sex>>stu[i].high;}

2. sort排序，依据男在左，女在右。当性别一致，则按身高排序，男生身高从小到大，女生则从高到低。

bool cmp(Student x,Student y){if(x.sex!=y.sex){return x.sex>y.sex;}else{if(x.sex=="male"){return x.high<y.high;}return x.high>y.high;}
}

3. 最后输出
   总代码：

//1182：合影效果
#include<bits/stdc++.h>
using namespace std;
struct Student{string sex;double high;
};
bool cmp(Student x,Student y){if(x.sex!=y.sex){return x.sex>y.sex;}else{if(x.sex=="male"){return x.high<y.high;}return x.high>y.high;}
}
int main(){Student stu[105];int n;cin>>n;for(int i=0;i<n;i++){cin>>stu[i].sex>>stu[i].high;}sort(stu,stu+n,cmp);for(int i=0;i<n;i++){printf("%.2f ",stu[i].high);}return 0;
}

1183：病人排队

根据题目：我们可分为老年人看病 与 非老年人看病 的排队顺序。病人有病号与年龄两个属性。老规矩用结构体。

1. 一个病人要有ID、年龄、排号顺序。定义结构体并输入；

struct Per{string id;int age,num;
};int main(){Per p[105];Per a[105], b[105]; //a是老年人 b是非老年人int n,len1=1,len2=1;	cin>>n;for(int i=1;i<=n;i++){cin>>p[i].id>>p[i].age;}

2. 通过判断年龄>=60，进行分类，老年人a数组， 非老年人b数组。

	for(int i=1;i<=n;i++){if(p[i].age>=60){a[len1].num = len1;a[len1].age = p[i].age;a[len1++].id = p[i].id;}else{b[len2++].id = p[i].id;}}

3.对a数组老年人进行sort排序，年龄从大到小，当年龄相同按排号登记顺序先后。

bool cmp(Per x,Per y){if(x.age!=y.age) return x.age>y.age;else if(x.age==y.age) return x.num<y.num;
}sort(a+1,a+1+len1,cmp);

4.排完序后，进行输出，先输出老年人再输出非老年人。

for(int i=1;i<len1;i++) cout<<a[i].id<<endl;
for(int j=1;j<=len2;j++) cout<<b[j].id<<endl;

总代码：

//1183：病人排队
#include<bits/stdc++.h>
using namespace std;
struct Per{string id;int age,num;
};
bool cmp(Per x,Per y){if(x.age!=y.age) return x.age>y.age;else if(x.age==y.age) return x.num<y.num;
}
int main(){Per p[105];Per a[105], b[105];int n,len1=1,len2=1;	cin>>n;for(int i=1;i<=n;i++){cin>>p[i].id>>p[i].age;}for(int i=1;i<=n;i++){if(p[i].age>=60){a[len1].num = len1;a[len1].age = p[i].age;a[len1++].id = p[i].id;}else{b[len2++].id = p[i].id;}}sort(a+1,a+1+len1,cmp);for(int i=1;i<len1;i++) cout<<a[i].id<<endl;for(int j=1;j<=len2;j++) cout<<b[j].id<<endl;return 0;
} 

1184：明明的随机数

由题目可知，去重与排序，我们可用 “桶排序” 做，很方便。

1. 统计桶的数量，这样每个桶的值只输出一次，那就不会有重复的！

#include<bits/stdc++.h>
using namespace std;
int a[10000],b[10000]; //默认数组值0 
int main(){//4.桶排序int n,x,cnt=0;cin>>n;for(int i=1;i<=n;i++){cin>>x; // 4 4 5 9 a[x]=a[x]+1; //统计桶的数量 } 

2. 判断有桶号，只执行一次，就可以去重

	for(int i=0;i<1000;i++) {if(a[i]>0){ //有数量 b[cnt++]=i; //b去重 排好序 }}

3. 最后输出个数与值。
   总代码：

#include<bits/stdc++.h>
using namespace std;
int a[10000],b[10000]; //默认数组值0 
int main(){//4.桶排序int n,x,cnt=0;cin>>n;for(int i=1;i<=n;i++){cin>>x; // 4 4 5 9 a[x]=a[x]+1; //统计桶的数量 } for(int i=0;i<1000;i++) {if(a[i]>0){ //有数量 b[cnt++]=i; //b去重 排好序 }}cout<<cnt<<endl;for(int i=0;i<cnt;i++){cout<<b[i]<<" ";} return 0;
}

1185：单词排序

由题目可知，需要输入多个字符串，我们可以定义字符串的数组s进行输入。
用到一维数组的输入，排序我们直接用sort即可。
但是我们重复的只能输出一次，那排序后，重复的单词会在相邻位置，只要判断数组前一个与后一个的值不等就存到另外一个数组ss。
遍历完所有字符串就，输出数组ss。

//1185：单词排序
#include<bits/stdc++.h>
using namespace std;
int main(){int i=0,k=0;string s[105],ss[105];while(cin>>s[i]){i++;}sort(s,s+i);for(int j=1;j<i;j++){if(s[j-1]!=s[j]) ss[k++]=s[j-1];}if(s[i-2]!=s[i-1]) ss[k++] = s[i-1];for(int i=0;i<k;i++){cout<<ss[i]<<endl;}return 0;
} 

//1185：单词排序
#include<bits/stdc++.h>
using namespace std;
int main(){int i=0,k=0;string s[105];while(cin>>s[i]){i++;}sort(s,s+i);for(int j=1;j<=i;j++){if(s[j-1]!=s[j]){cout<<s[j-1]<<endl;}}return 0;
} 

1186：出现次数超过一半的数

通过题目可知，我们要找次数超过一半的数，那我们要统计每个数的次数，可用桶排序；但要注意，数组的值是有-50的，所以我们可以让每个数组编号+50再统计。

int x,b[1005]={0};
int main(){int n,flag=0;cin>>n; for(int i=0;i<n;i++){cin>>x;b[x+50]++; //注意数值有负 }

统计完只要在0到1000值内判断，数组值>n/2，就可以输出 编号值-50。
注意细节，要是没有满足if条件则没有找到，要输出no。

//1186：出现次数超过一半的数
#include<bits/stdc++.h>
using namespace std;
int x,b[1005]={0};
int main(){int n,flag=0;cin>>n; for(int i=0;i<n;i++){cin>>x;b[x+50]++; //注意数值有负 }for(int i=0;i<1000;i++){if(b[i]>n/2){cout<<i-50<<endl;flag=1; break;}}if(flag==0){cout<<"no"<<endl;}return 0;
} 

1187：统计字符数

统计个数，现在我们可以用桶排序方便。统计完每个字母的次数，我们在从a到z判断哪个字母的次数最多，找出来最大值。

//1187：统计字符数
#include<bits/stdc++.h>
using namespace std;
int b[1000];
int main(){string s;char c;int max=0;cin>>s;for(int i=0;i<s.size();i++){b[s[i]]++;	} for(int i='a';i<='z';i++){if(max<b[i]){max = b[i]; //记录数量最大值 c=i; }}cout<<c<<" "<<max<<endl;return 0;
}