在本章中将介绍各种各样实用的提高我们编程效率的小技巧和模版库。其中绝大多数依靠C++自带类和函数实现。
第一节 排序算法
排序算法为竞赛中最常用的算法之一，我们可以利用C++自带的库函数进行排序。
使用排序算法必须包含 algorithm 头文件
自带排序算法的一般形式为：
//将数组arr的下标为m的元素到下标为n-1的元素进行从小到大排序
sort(arr+m,arr+n);
sort(arr+m,arr+n,comp); //与sort(arr+m,arr+n)相比，这个写法可以自己定义排序的规则
//其中，comp为自定义的函数
对于sort(arr+m,arr+n) 我们举个简单的例子：
//这个程序实现从键盘读入10个数，然后从小到大输出的功能
#include<iostream>
#include<algorithm>
using namespace std;
int a[10];
int main()
{
for (int i=0;i<10;++i) cin>>a[i];
sort(a+0,a+10);
for (int i=0;i<10;++i) cout<<a[i]<<‘ ‘;
cout<<endl;
return 0;
}
当然，有时我们需要从大到小的进行排序。那么我们可以用sort(arr+n,arr+m,comp)进行排序。
不过，在调用sort(arr+n,arr+m,comp) 之前我们需要自己写个 comp函数。
从大到小排序的comp函数可以这样写：
int my_comp(const int & a,const int & b)
{
return a>b; //在两元素相同时一定要返回 0 或者 false
} //comp函数的名字是由我们自己决定的，例如可以叫cat_cat,dog_dog 等等
//程序实现从键盘读入10个数，然后从大到小输出的功能
#include<iostream>
#include<algorithm>
using namespace std;
int a[10];
int my_comp(const int & a,const int & b)
{
return a>b; //如果a>b 则返回1 ，否则返回 0
}
int main()
{
for (int i=0;i<10;++i) cin>>a[i];
sort(a+0,a+10,my_comp);
for (int i=0;i<10;++i) cout<<a[i]<<‘ ‘;
cout<<endl;
return 0;
}
在更多情况下，我们不仅对一个特征进行排序，而是多个特征。例如将学生的成绩进行排序，当然用上面的做法是行不通的。这时，我们就想到了结构体这种数据类型。当我们采用sort()函数的默认规则排序结构体时，sort()默认结构体中的第一个成员为第一关键字，第二个成员为第二关键字，……，第N个元素为第N关键字，然后从小到大排序。
例如我们要将学生的成绩从大到小排序，当成绩相同时，根据姓名字典序小的优先的规则排进行序。显然我们无法采用默认规则进行排序。
这时我们可以定义这样的comp:
int score_comp(const student & a,const student & b)
{
if (a.score>b.score) return 1;
if (a.score<b.score) return 0;
if (a.name<b.name) return 1;
return 0;
}
例8.1 每当考试结束，老师总要对学生的成绩进行排序，以便研究学生学习情况。老师发现学生数目庞大，所以找来了会编程的你，并且它给你了全部同学的分数，希望你能按如下规则排序：1.分数高的排在前面；2.如果分数相同，就把名字字典序低的放在前面。
【输入格式】
第一行一个整数n
接下来n行每行一个学生名字和一个分数。inameiscore
【输出格式】
每行一个名字和一个分数
【输入样例】
3 Xiaoxiao 396
Yingmo 405
Diyucailang 399
【输出样例】
Yingmo 405
Diyucailang 399
Xiaoxiao 396
【参考程序】
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
struct student{
int score;
string name;
}a[100];
int n;
int score_comp(const student & a,const student & b)
{
if (a.score>b.score) return 1;
if (a.score<b.score) return 0;
if (a.name<b.name) return 1;
return 0;
}
int main()
{
cin>>n;
for (int i=0;i<n;++i)
{
cin>>a[i].name;
cin>>a[i].score;
}
sort(a+0,a+n,score_comp);
for (int i=0;i<n;++i)
cout<<a[i].name<<‘ ‘<<a[i].score<<endl;
return 0;
}
本文为原创文章，转载请注明出处！