洛谷P1104 生日

原题传送门

Description

已知 (n) 个人的姓名和出生年龄。请按照年龄由大到小对姓名进行排序。

注 : 如果有两个同学生日相同，输入靠后的同学先输出。

Solution

显然的 结构体排序 模板题

用一个 struct ，再写一个自定义 cmp 的 sort 足矣。

考虑如何写 cmp。

这里我们直接用写好的 cmp 进行分析。

inline bool cmp(Information a,Information b){
	if(a.y!=b.y) return a.y<b.y;
	else{
		if(a.m!=b.m) return a.m<b.m;
		else{
			if(a.d!=b.d) return a.d<b.d;
			else return a.turn>b.turn;
		}
	}
}

首先思路很简单，按照 年-月-日 的顺序依次进行比较。

这里有一个点在于根据年龄由大到小 ( eq) 根据生日日期大小排序。

而应为 生日日期大的反而小，生日日期小的反而大。道理也很显然。

而又根据 :

如果有两个同学生日相同，输入靠后的同学先输出。

这里 sort 是不稳定的排序，虽然 STL 中也有对应的稳定排序的函数，但我认为用一个 turn 记录下输入顺序会更加方便。

其余按照题意即可。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int Maxn=110;
struct Information{
	char name[20];
	int y,m,d;
	int turn;
}p[Maxn];
inline void read(int &x){
	int f=1;
	char ch=getchar();
	x=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar();
	}
	x*=f;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int n;
inline bool cmp(Information a,Information b){
	if(a.y!=b.y) return a.y<b.y;
	else{
		if(a.m!=b.m) return a.m<b.m;
		else{
			if(a.d!=b.d) return a.d<b.d;
			else return a.turn>b.turn;
		}
	}
}
int main(){
	//freopen("read.txt","r",stdin);
	read(n);
	for(int i=1;i<=n;i++){
		scanf("%s",p[i].name);
		read(p[i].y);read(p[i].m);read(p[i].d);
		p[i].turn=i;
	}
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;i++) printf("%s
",p[i].name);
	return 0;
}