sort函数自定义排序

sort函数自定义排序

咳咳，自定义排序说实话用的地方还是很多的，像ACM里面，天梯赛里面，特别是天梯，必出这玩意。。。咳咳，水点字数，咱继续。

• 首先哈，我们来看一下c++自带的排序；

• 可以看出哈，默认是按升序排序的。

• sort不但可以对整型进行排序还能对字符串进行排序。

• 咳咳，好像讲偏了哈，今天主要是讲自定义排序哈，c++自带的只是排升序，但是我要排降序怎么办呢。这个时候就需要我们自定义排序了。

• 这里我们可以看到那个cmp比较函数哈，排序规则也很简单，你想着降序是大的在前面，所以前面的数大于后面的数，所以写成 a>b 就可以了。是不是很好记。而且，系统自带的sort排序也是快速排序，还是很香的。
• 这里是对数组进行排序，当出现结构的时候，有多个参数进行排序，其实可以直接在结构体里面进行cmp比较，然后直接sort就能够实现你想要的排序。
• 然后这里也有两种常见的写法。先来看看 cmp函数 吧！
• 题目： 我们第一阶级排序是对 x 进行排降序，在 x 相等的情况下，我们对 y 进行排升序。

bool cmp(node a,node b){
	if(a.x!=b.x)return a.x>b.x;
	return a.y<b.y;
}

• 我们只需要这样写就能完成对结构体多级阶级的排序了。
• 然后第二种常见的写法就是在结构体里面，对 小于号＜ 方法的重载，内部编写逻辑也能实现多级排序。

	bool operator <(const node &b)const{
		if(x!=b.x)return x>b.x;
		return y<b.y;
	} 

• 区别也不大，一个写在结构体里面，直接用sort就行，一个写个函数，加个函数名就行。萝卜白菜，各有所爱，所以你喜欢哪一种呢？
• 可能有人在问，你老是放图片干啥，直接放代码满，咳咳，我解释下哈，我觉得这个代码呢，需要你自己去打，多打，打了才会是你自己的。
• 咳咳，学到这里，差不多也应该会用了，然后我们现在来实战一下。

L2-009 抢红包 (25分)

题目链接：（点我看题<-----这是一个链接）

没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。

输入格式：
输入第一行给出一个正整数N（≤10^​4 ），即参与发红包和抢红包的总人数，则这些人从1到N编号。随后N行，第i行给出编号为i的人发红包的记录，格式如下：

K       N₁       P₁     N_k     P_k

其中K（0≤K≤20）是发出去的红包个数，N_i 是抢到红包的人的编号，P_i （>0）是其抢到的红包金额（以分为单位）。注意：对于同一个人发出的红包，每人最多只能抢1次，不能重复抢。

输出格式：
按照收入金额从高到低的递减顺序输出每个人的编号和收入金额（以元为单位，输出小数点后2位）。每个人的信息占一行，两数字间有1个空格。如果收入金额有并列，则按抢到红包的个数递减输出；如果还有并列，则按个人编号递增输出。

输入样例：

10
3 2 22 10 58 8 125
5 1 345 3 211 5 233 7 13 8 101
1 7 8800
2 1 1000 2 1000
2 4 250 10 320
6 5 11 9 22 8 33 7 44 10 55 4 2
1 3 8800
2 1 23 2 123
1 8 250
4 2 121 4 516 7 112 9 10

输出样例：

1 11.63
2 3.63
8 3.63
3 2.11
7 1.69
6 -1.67
9 -2.18
10 -3.26
5 -3.26
4 -12.32

• 这题根据题目要求，要对三个阶级进行排序，先按 收入 排 降序 ，如果收入相等，那就按照 抢到红包的个数 进行排 降序 ，最后如何红包的个数也相等，那就按照 个人的编号 进行排 升序 。
• 好了，了解他们的结构以后呢，那就可以写了，先建立数据结构，然后按照题目意思进行读取值并累计。
• 代码如下：

#include<bits/stdc++.h>
using namespace std;
struct node{
	int id;   
	int fa;   
	int fachu;   
	int k ;   
	float shouru;
	/*      这是小于号的重载       */
    bool operator <(const node &b)const{
        if(shouru!=b.shouru)return shouru>b.shouru;
        else if(k!=b.k)return k>b.k;
        return id<b.id;
    }
}a[110000];

/*      这是cmp函数       */
// bool cmp(struct node a , struct node b){
// 		if(a.shouru!=b.shouru)return a.shouru>b.shouru;
// 		else if(a.k!=b.k) return a.k>b.k;
// 		else return a.id<b.id;
// }

int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		a[i].id = i;
		int k;
		cin>>k;
		int sum = 0;
		
		while(k--)
		{
			int id, s;
			cin>>id>>s;
			sum = sum+s;
			a[id].fachu = a[id].fachu+s;
			a[id].k++;
		}
		a[i].fa = sum;
	}

	for(int i=1;i<=n;i++)
		a[i].shouru = (a[i].fachu - a[i].fa)*1.0/100;
		
	sort(a+1,a+n+1);      //小于号重载使用
//	sort(a+1,a+n+1,cmp);   函数使用
	
	for(int i=1;i<=n;i++) printf("%d %.2f\n",a[i].id,a[i].shouru);
	return 0;
}

• ok，今天的自定义就到这了，我干饭去了。。。。
• 隶属于算法竞赛入门到进阶完整学习路线 <-----这是一个链接