结构体的sort排序
结构体⽤sort快排的⽅法
struct node{
int k,s;
}p[5005];
bool cmp1(node x,node y){
return x.s>y.s; //定义降序排序（从⼤到⼩）
}
bool cmp2(node x,node y){
return x.k<y.k; //定义升序排序（从⼩到⼤）
}
sort(p+1,p+n+1,cmp2); //排序
看题⽬，洛⾕p1068
题⽬描述
世博会志愿者的选拔⼯作正在 A 市如⽕如荼的进⾏。为了选拔最合适的⼈才，A市对所有报名的选⼿进⾏了笔试，笔试分数达到⾯试分数线的选⼿⽅可进⼊⾯试。⾯试分数线根据计划录取⼈数的150%划定，即如果计划录取m名志愿者，则⾯试分数线为排名第m×150%（向下取整）名的选⼿的分数，⽽最终进⼊⾯试的选⼿为笔试成绩不低于⾯试分数线的所有选⼿。
现在就请你编写程序划定⾯试分数线，并输出所有进⼊⾯试的选⼿的报名号和笔试成绩。
输⼊输出格式
输⼊格式：
第⼀⾏，两个整数 n,m(5 ≤ n ≤ 5000,3 ≤ m ≤ n)，中间⽤⼀个空格隔开，其中n表⽰报名参加笔试的选⼿总数，m表⽰计划录取的志愿者⼈数。输⼊数据保证 m×150%向下取整后⼩于等于 n。
第⼆⾏到第 n+1⾏，每⾏包括两个整数，中间⽤⼀个空格隔开，分别是选⼿的报名号 k(1000 ≤ k ≤ 9999)和该选⼿的笔试成绩s(1 ≤ s ≤ 100)。数据保证选⼿的报名号各不相同。
输出格式：
第⼀⾏，有2个整数，⽤⼀个空格隔开，第⼀个整数表⽰⾯试分数线；第⼆个整数为进⼊⾯试的选⼿的实际⼈数。
从第⼆⾏开始，每⾏包含2个整数，中间⽤⼀个空格隔开，分别表⽰进⼊⾯试的选⼿的报名号和笔试成绩，按照笔试成绩从⾼到低输出，如果成绩相同，则按报名号由⼩到⼤的顺序输出。
输⼊输出样例
输⼊样例#1：
6 3
1000 90
3239 88
2390 95
7231 84
1005 95
1001 88
输出样例#1：
88 5
2390 95
1000 90
1001 88
3239 88
说明
【样例说明】
m×150%=3×150%=4.5，向下取整后为4。保证44个⼈进⼊⾯试的分数线为88，但因为88有重分，所以所有成绩⼤于等于88 的选⼿都可以进⼊⾯试，故最终有5个⼈进⼊⾯试。
NOIP 2009 普及组第⼆题
这道题就是⼀个典型的结构体的排序
但是⾸先需要⾯试成绩的从⼤到⼩的排序，然后才是相同的成绩再去从⼩到⼤对编号去排序。sort out同义短语
⽽sort是⼀个不稳定的排序，因为当数据量稍⼤时，sort()就会使⽤快速排序，⽽快速排序是不稳定排序，即不能保证原序列中相等的元素在排序后保持相对位置不变。
即如果排序之后的两者成绩相同，但是由于快排是不停的交换位置的排序，所以相同成绩的两者的相对位置会变换，所以造成的不稳定排序。
稳定排序的概念：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r [ i ]=r [ j ]，且r [ i ]在r [ j ]之前，⽽在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
所以这题应该⽤的是STL⾥⾯的稳定排序stable_sort。
AC代码：
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int k,s;
}p[5005];
bool cmp1(node x,node y){
return x.s>y.s; //定义降序排序（从⼤到⼩）
}
bool cmp2(node x,node y){
return x.k<y.k; //定义升序排序（从⼩到⼤）
}
int main(){
int n,m;
cin>>n>>m;
m=m*15/10;
for(int i=1;i<=n;i++){
cin>>p[i].k>>p[i].s;
}
sort(p+1,p+n+1,cmp2); //快排排序
stable_sort(p+1,p+n+1,cmp1); //稳定排序
cout<<p[m].s<<"";
for(int i=m+1;i<=n;i++){
if(p[i].s==p[m].s){
}
else break;
}
cout<<m<<endl;
for(int i=1;i<=m;i++){
cout<<p[i].k<<""<<p[i].s<<endl;
}
return0;
}
还有⼀种是对字符串的结构体sort排序。
题⽬背景
宇宙总统竞选
题⽬描述
地球历公元6036年，全宇宙准备竞选⼀个最贤能的⼈当总统，共有n个⾮凡拔尖的⼈竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。
输⼊输出格式
输⼊格式：
president.in
第⼀⾏为⼀个整数n，代表竞选总统的⼈数。
接下来有n⾏，分别为第⼀个候选⼈到第n个候选⼈的票数。
输出格式：
president.out
共两⾏，第⼀⾏是⼀个整数m，为当上总统的⼈的号数。
第⼆⾏是当上总统的⼈的选票。
输⼊输出样例
输⼊样例#1：
5
98765
12365
87954
1022356
985678
输出样例#1：
4
1022356
说明
票数可能会很⼤，可能会到100位数字。n<=20
AC代码：
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct{
string str;
int p;
}aaa;
bool cmp(aaa a,aaa b){
if(a.str.size()==b.str.size()){
return a.str<b.str;
}
return a.str.size()<b.str.size();
}
int main(){
aaa m[22];
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>m[i].str;
m[i].p=i;
}
sort(m+1,m+n+1,cmp);
cout<<m[n].p<<endl<<m[n].str;
return0;
}
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论