题解 P1104 【生日】
_jimmywang_ · · 题解
我又来了！
首先，题目标签是：
字符串 &排序 &模拟 &选择排序
然而我们不用玄学的选择排序，我们来引进一种更加简（xuan）单（xue）的排序方法：
快速排序！！！！
首先推荐一个网站：算法可视化
看到这里的人去该网站看快排的图示，肯定要比我讲的好的多…………
快排呢，用的是分治法。先找一个基准数，把比他小的放他左边，比他大的放他右边，再递归左边和右边。
好吧，我承认我讲不清楚，看图吧…………
6个数：5,7,6,4,3,8.
---
--- | |
| | --- | |
--- | | | | | |
| 5 | | | | | --- | 8 |
| | | 7 | | | | | --- | |
| 基| | | | 6 | | | | | | |
| 准| | | | | | 4 | | 3 | | |
| | | | | | | | | | | |
--- --- --- --- --- --- 把3和4移到5左边，剩下的在5右边。
---
--- | |
| | --- | |
--- | | | | | |
--- | 5 | | | | | | 8 |
| | --- |基 | | 7 | | | | |
| | | | |准 | | | | | | |
| 4 | | 3 | | | | | | 6 | | |
| | | | | | | | | | | |
--- --- --- --- --- ---
这样就确定了5的位置。
递归左边，3和4交换。
---
--- | |
| | --- | |
--- | | | | | |
--- | 5 | | | | | | 8 |
--- | | |基 | | 7 | | | | |
| | | | |准 | | | | | | |
| 3 | | 4 | | | | | | 6 | | |
| | | | | | | | | | | |
--- --- --- --- --- ---
这样，3,4,5的位置就确定了。
再递归右边
---
--- | |
--- | | | |
--- | | | | | |
--- | 5 | | | | | | 8 |
--- | | |基 | | 6 | | 7 | | |
| | | | |准 | | | | | | |
| 3 | | 4 | | | | | | | | |
| | | | | | | | | | | |
--- --- --- --- --- ---
排好了QWQ
回到本题：
#include<bits/stdc++.h>
using namespace std;
struct node//结构体排序
{
string s;//名字
int n,y,r,num;//年，月，日，输入的编号。
}a[110];
int n;
bool cmp(node a,node b)
{
if(a.n<b.n)return 1;//先比年
if(a.n>b.n)return 0;
if(a.n==b.n)
{
if(a.y<b.y)return 1;//再比月
if(a.y>b.y)return 0;
if(a.y==b.y)
{
if(a.r<b.r)return 1;//再比日
if(a.r>b.r)return 0;
if(a.r==b.r)
{
if(a.num>b.num)return 1;//最后比编号
else return 0;
}
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i].s>>a[i].n>>a[i].y>>a[i].r,a[i].num=i;//输入
sort(a+1,a+n+1,cmp);//快排
for(int i=1;i<=n;i++)cout<<a[i].s<<endl;//输出。
return 0;
}