37结构体应用_讲义 知识清单 1、结构体数组排序【应用】 第37课结构体应用 2、如何书写复杂的排序规则【应用】当有多个结构变量存储在数组中时，有时需要按照既定的排序规则给结构体数组排序，那么我们就可以用到前面学习过的sort函数，帮助我们解决问题。 一、回顾sort函数 格式 sort(待排序范围的起始位置，待排序范围的末尾后一个位置) 功能 对数组元素进行排序，默认升序。 示例 1 int a[10]={3,1,4,5,6,8,9,3,4,0}; 2 sort(a+0,a+10);//对数组a全部数据a[0]~a[9]进行从小到大排序 3 sort(a+3,a+8);//对a[3]～a[7]的数据进行从小到大排序 4 sort(a+1,a+9);//对数组第2～9个元素的数据进行从小到大排序 二、结构体数组与sort函数 因为结构体有很多属性，按照什么规则来排序呢，sort函数并不知道。所以我们还需要sort函数的第三个参数。这个参数一般会起名叫cmp，比较的意思。用cmp函数，告诉sort函数按照怎样的规则对数组进行排序。仍用神兽来举例，对神兽的等级进行排序：bool cmp1(monster a,monster b){  1 return a.level<b.level; 2 }  3 sort(mons+1,mons+4+1,cmp1); //按照等级从低到高排序 4 bool cmp2(monster a,monster b){  1 return a.level>b.level; 2 }  3 sort(mons+1,mons+4+1,cmp2); //按照等级从高到低排序 4 例1：(2651)培训 【题目描述】 某培训机构的学员有如下信息： 姓名（字符串，不超过10个字符） 去年 NOIP 成绩（整数，NOIP 满分是 600 分） 输入学员信息，按照成绩从高到低的顺序，输出学员信息。 【输入】 第一行输入一个正整数 n(1≤n≤50)，表示学员个数。 第二行开始往下 n 行。每行首先是一个字符串表示学员姓名，再是一个整数为去年 NOIP 成绩，保证成绩互不相同。 【输出】 输出 n 行，每行首先输出一个字符串表示学生姓名，去年的 NOIP 成绩。以空格隔开。【输入样例】 3 1 kkk 0 2 chen 600 3 bob 480 4 【输出样例】 chen 600 1 bob 480 2 kkk 0 3 解答 #include <bits/stdc++.h> 1 using namespace std; 2 struct stu{ 3 string name; 4 int score; 5 }s[55]; 6 bool cmp(stu a,stu b){ 7 return a.score>b.score; 8 } 9 int main(){ 10 int n; 11 cin>>n; 12 for(int i=1;i<=n;i++){ 13 cin>>s[i].name>>s[i].score; 14 } 15 sort(s+1,s+n+1,cmp); 16 for(int i=1;i<=n;i++){ 17 cout<<s[i].name<<" "<<s[i].score<<endl; 18 } 19 return 0; 20 } 21 三、复杂的比较规则 当排序规则较为复杂时，我们可以按照一定的思路来写cmp函数。  规则1：先按照level排名，高的在前；  规则2：当level相同时，atk高的在前；  规则3：当atk相同时，hp高的在前。 bool cmp(monster a,monster b){ 1     if(a.level!=b.level) return a.level>b.level; 2     if(a.atk!=b.atk) return a.atk>b.atk; 3     return a.hp>b.hp; 4 } 5 例2：(2082)01串排队 【题目描述】 将 01 串首先按长度排序（短的在前），长度相同时，按1的个数多少进行排序（少的在前），1 的个数相同时再按 ASCII 码值排序（字典序小的在前）。 【输入】 第一行输入一个整数 n (1≤n≤100)，表示字符串的个数。 输入数据中含有一些 01 串，01 串的长度不大于 256 个字符。 【输出】 重新排列 01 串的顺序，使得串按基本描述的方式排序，然后依次输出。 【输入样例】 6 1 10011111 2 00001101 3 1010101 4 1 5 0 6 1100 7 【输出样例】 0 1 1 2 1100 3 1010101 4 00001101 5 10011111 6 分析 首先确定一下如何定义结构体，和确定排序规则。 struct Str{  1     string str;  //字符串 2     int len;     //长度 3     int num;     //1的个数 4 }s[105];  5 输入信息时依次赋值： for(int i=1;i<=n;i++){ 1     string ss; 2     cin>>ss; 3     s[i].str=ss; 4     s[i].len=ss.size(); 5     s[i].num=cnt1(ss); //将功能性的代码写进函数里，使得主函数代码逻辑更清晰。6 }  7 排序规则为： 规则1：先按照长度排名，短的在前； 规则2：当长度相同时，按1的个数多少进行排序，少的在前； 规则3：当1的个数相同时，字典序小的在前。 bool cmp(Str a,Str b){ 1     if(a.len!=b.len) return a.len<b.len; 2     if(a.num!=b.num) return a.num<b.num; 3     return a.str<b.str; 4 } 5 解答 1 #include <bits/stdc++.h> 2 using namespace std; 3 struct Str{ 4     string str; 5     int len,num; 6 }s[105]; 7 bool cmp(Str a,Str b){ 8     if(a.len!=b.len) return a.len<b.len; 9     if(a.num!=b.num) return a.num<b.num; 10     return a.str<b.str; 11 } 12 int cnt1(string x){ 13     int cnt=0; 14     for(int i=0;i<x.size();i++){ 15         if(x[i]'1') cnt++; 16 } 17     return cnt; 18 } 19 int main(){ 20     int n; 21     cin>>n; 22     for(int i=1;i<=n;i++){ 23         string ss; 24         cin>>ss; 25         s[i].str=ss; 26         s[i].len=ss.size(); 27         s[i].num=cnt1(ss); 28     }  29     sort(s+1,s+n+1,cmp); 30     for(int i=1;i<=n;i++){ 31         cout<<s[i].str<<endl; 32     } 33     return 0; 34 }例3：(2652)年龄排序Ⅱ 【题目描述】 输入 n 个学生的信息，包括姓名、出生年月。要求按年龄从小到大依次输出这些学生的姓名。如果有同年同月出生，按输入顺序，早的在前。 【输入】 第一行一个整数 n (n≤100)，表示学生人数。 接下来 n 行，每一行依次输入学生的姓名（长度不超过 40）、性别（长度不超过 10）、出生年份、出生月份。 【输出】 按照年龄从小到大，一行输出一个学生的的姓名。 【输入样例】 5 1 John male 1999 12 2 David female 1998 8 3 Jason male 1998 11 4 Jack female 1998 8 5 Kitty female 2000 7 6 【输出样例】 Kitty 1 John 2 Jason 3 David 4 Jack 5 分析 有时，题目中并不会直接给出结构体的所有信息，我们就要根据排序规则来确定需要哪些成员变量。 排序规则为： 规则1：先按年份排序，大的在前； 规则2：当年份相同时，按月份排序，大的在前； 规则3：当月份相同时，先输入的在前。 struct Stu{  1     string name,gender;  //姓名 性别  2     int year;            //年份 3     int month;           //月份 4     int id;              //还需要输入序号 5 }s[105];  6 解答 1 #include <bits/stdc++.h> 2 using namespace std; 3 struct Stu{  4     string name,gender;  5     int year,month,id; 6 }s[105];  7 bool cmp(Stu a,Stu b){ 8     if(a.year!=b.year) return a.year>b.year; 9     if(a.month!=b.month) return a.month>b.month; 10     return a.id<b.id; 11 } 12 int main(){ 13     int n; 14     cin>>n; 15     for(int i=1;i<=n;i++){ 16         cin>>s[i].name>>s[i].gender>>s[i].year>>s[i].month;  17         s[i].id=i; 18     }  19     sort(s+1,s+n+1,cmp); 20     for(int i=1;i<=n;i++){ 21         cout<<s[i].name<<endl; 22     } 23     return 0; 24 } 例4：(2653)男孩 vs 女孩 【题目描述】 给定 N 个学生的成绩信息，请你求出女生第一名与男生倒数第一名的分数差距。 【输入】 第一行输入整数 N(1≤n≤100)，表示学生数量。 接下来 N 行，每行包含一个学生的姓名，性别，ID和成绩。其中姓名和ID是长度不超过 10 且不包含空格的字符串。性别为 F（女）或 M（男）。成绩是一个范围在 [0,100] 的整数。保证所有学生的成绩互不相同。 【输出】 输出女生第一名的成绩减去男生倒数第一名的成绩的差。 如果不存在某个性别的学生，则输出 NA。 【输入样例】 3 1 Joe M Math990112 89 2 Mike M CS991301 100 3 Mary F EE990830 95 4 【输出样例】 6 1分析 很容易想到第一种方法： 一个女生数组，成绩从低到高排序，一个男生数组，成绩从低到高排序。如果没有女生或者没有男生，输出 NA，否则输出分差。分差 = 女生最高分 - 男生最低分。 我们再来想另一种方法，如果女生和男生一起排序，只需要一个数组就可以了。  规则1：先按性别排序，将所有女生排在男生前面  规则2：如果性别相同，分数高的在前 如果第一位不是女生或者最后一位不是男生，输出 NA，否则输出分差。分差 = 第一位的分数 - 最后一位的分数。 解答 1 #include <bits/stdc++.h> 2 using namespace std; 3 struct Stu{  4     string name,id;  //姓名 ID  5     char gender;     //性别 6     int score;       //分数 7 }s[105];  8 bool cmp(Stu a,Stu b){ 9 //女生排在男生前面，字符F的ASCII码值小于字符M 10     if(a.gender!=b.gender) return a.gender<b.gender; 11     return a.score>b.score; 12 } 13 int main(){ 14     int n; 15     cin>>n; 16     for(int i=1;i<=n;i++){ 17         cin>>s[i].name>>s[i].gender>>s[i].id>>s[i].score;  18     }  19     sort(s+1,s+n+1,cmp); 20     if(s[1].gender!='F'||s[n].gender!='M') cout<<"NA"; 21     else cout<<s[1].score-s[n].score; 22     return 0; 23 } 第一种方法代码： #include <bits/stdc++.h> 1 using namespace std; 2 struct Stu{ 3 string name,id; //姓名 ID 4 char gender; //性别 5 int score; //分数 6 }girl[105],boy[105]; 7 bool cmp(Stu a,Stu b){ 8 return a.score<b.score; 9 } 10 int main(){ 11 int n,g=0,b=0; 12 cin>>n; 13 for(int i=1;i<=n;i++){ 14 Stu tmp; 15 cin>>tmp.name>>tmp.gender>>tmp.id>>tmp.score; 16 if(tmp.gender'F') girl[++g]=tmp; 17 else boy[++b]=tmp; 18 } 19 sort(girl+1,girl+g+1,cmp); 20 sort(boy+1,boy+b+1,cmp); 21 if(g0||b0) cout<<"NA"; 22 else cout<<girl[g].score-boy[1].score; 23 return 0; 24 } 25 例5：(1354)Petya的生日 【题目描述】 Petya要过生日了，他有n道想吃的菜，但是他又不会烧，所以就在线点菜了。 不幸的是他想吃的菜都来自不同的餐厅，而且现在又是高峰期，配送可能很慢，为了能早点吃饭，他决定选择一些菜自己去店里拿(当然可以不选)。 准确的说第i道菜如果让商家配送需要ai 分钟到达，自己去拿需要bi 分钟，那么Petya最快几点能吃饭呢？你可以认为所有餐厅都是不顺路的并且只有菜到齐了Petya才会吃饭【输入】 第一行一个正整数n (1≤n≤20)。 第二行n个正整数a1​,a2​,...,an​(1≤ai​≤100)。 第三行n个正整数b1​,b2​,...,bn ​(1≤bi​≤100)。 【输出】 一个数表示Petya最快多久能吃饭。 【输入样例】 4 1 3 7 4 5 2 2 1 2 4 3 【输出样例】 5 1分析 假设某一道菜x由商家配送，那么商家配送时间不超过菜1的配送时间的，都可以选择让商家配送。因为可以同时送，所以这些菜的总配送时间就是由x的配送时间来决定。 那么就需要按照商家的配送时间排序，短的在前。 最优解可能是全部商家送，可能全部自提，可能混合商家送和自提。所以我们需要枚举出所有情况，来找出最优解！ 每个方案的具体做法就是，排好序之后，以某道菜的配送时间作为标准，枚举这道菜。这道菜左侧包括这道菜，全都由商家配送，这道菜左侧全都自提。那么总耗时就是，配送耗时为标准菜的配送时间，自提耗时为所有自提菜的总时间。两者取最大值。 在所有方案耗时中，取一个最小值作为答案。 解答 #include <bits/stdc++.h> 1 using namespace std; 2 struct food{  3     int ps,zt;       //配送  自提 4 }f[25];  5 bool cmp(food a,food b){ 6     return a.ps < b.ps; 7 } 8 int main(){ 9     int n; 10     cin>>n; 11     for(int i=1;i<=n;i++) cin>>f[i].ps; 12     for(int i=1;i<=n;i++) cin>>f[i].zt; 13     sort(f+1,f+n+1,cmp); 14     int ans=2000; 15     for(int i=0;i<=n;i++){ //当i=0时，就是全自提的情况 16         int sum=0; //商家自提总耗时  17         for(int j=i+1;j<=n;j++){ 18             sum+=f[j].zt; 19         } 20         int t=max(sum,f[i].ps); //f[i].a为商家配送时间 21         ans=min(ans,t); 22     } 23     cout<<ans; 24     return 0; 25 } 26作业 编程题（请在OJ平台上完成） 1、（1081）成绩排名 2、（1337）篮球队选拔