在做排序算法的基础题的时候。如果一个对象里面多个元素需要进行排序,那么用结构体加cmp,对sort的排序进行改写,就能达到一个很好的效果。
P1781 宇宙总统
题目描述
地球历公元 6036 年,全宇宙准备竞选一个最贤能的人当总统,共有 n 个非凡拔尖的人竞选总统,现在票数已经统计完毕,请你算出谁能够当上总统。
输入输出样式
1 2 3 4 5 6
| 5 98765 12365 87954 1022356 985678
|
解题思路
其实这个题目就需要考虑到字符串长度的比较和在相同长度下数字的大小,然后这就是用字符串的比较通过字典数来进行。然后每个候选人的序号都需要存储,所有这个就有多个元素需要存储和排序,因此用结构体是一个比较好的选择。
对于cmp的写法
1 2 3 4 5 6
| bool cmp(houxuan a,houxuan b){ if(a.len!=b.len) return a.len>b.len; else{ return a.votes>b.votes; } }
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
| #include<iostream> #include<algorithm> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<queue> #include<stack> #include<cmath> #include<string> using namespace std; typedef long long ll; constexpr int N = 21; struct houxuan{ int num; int len; string votes; }houxuans[N];
bool cmp(houxuan a,houxuan b){ if(a.len!=b.len) return a.len>b.len; else{ return a.votes>b.votes; } }
void solve(){ int n; cin>>n; for(int i = 0;i<n;i++){ houxuans[i].num = i+1; string s; cin>>s; houxuans[i].votes = s; houxuans[i].len = houxuans[i].votes.size(); } sort(houxuans,houxuans+n,cmp); cout<<houxuans[0].num<<endl; cout<<houxuans[0].votes; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); solve(); return 0; }
|
还有类似的简单题目就是在 P1093(洛谷上),也是用结构体排序的简单题目。