洛谷【P1104】生日（选择排序版）

题目传送门：https://www.luogu.org/problemnew/show/P1104

题目很简单，不过我是来讲选择排序的。

选择排序\((Selection sort)\)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。

然后我们重载一下运算符，直接排序就可以了。

时间复杂度：\(O(n^2)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

int n;

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

struct OIer {

	char s[20];

	int year,month,day,id;

	bool operator<(const OIer &a)const {

		if(year==a.year&&month==a.month&&day==a.day)return id>a.id;//如果同年同月同日生那就先输出id大的，不要粗心看漏了

		if(year==a.year&&month==a.month)return day<a.day;

		if(year==a.year)return month<a.month;

		return year<a.year;

	}//按照题意比较

}O[105];

int main() {

	n=read();

	for(int i=1;i<=n;i++) {

		O[i].id=i;

		scanf("%s%d%d%d",O[i].s,&O[i].year,&O[i].month,&O[i].day);

	}

	for(int i=1;i<n;i++) {

		int pos=i;//准备把第i大的找出来

		for(int j=i+1;j<=n;j++)//在接下来的人里找出生年月小的

			if(O[j]<O[pos])pos=j;

		swap(O[i],O[pos]);

	}

	for(int i=1;i<=n;i++)

		printf("%s\n",O[i].s);

	return 0;

}

巴特西

洛谷【P1104】生日（选择排序版）

最新文章

热门文章