E2-B coming 1CLR

题目

时间限制：200ms 1CLR2021 马上就要截稿了！但是柯柯还在 rush 实验…

为了速速完成论文的 related work，柯柯一下子下载了非常多的相关文献。柯柯开始整理文献，他先按照年份降序排好文献；对于同一年的文献，他再按字典序升序排列。

因为马上就要截稿了，柯柯必须尽早开始阅读文献。你能快点帮他把文献排下序吗？

输入 第一行是一个正整数 n 代表待排序的文献的个数。

接下来 n 行，每行一个数字 y 和字符串 c，分别代表该篇文献的发表年份和所属会议名称。

输出 输出 n 行，代表排序后（先按年份降序，同一年的再按字典序升序）的每篇文献。

输入样例 5 2017 1CLR 2016 1CLR 2016 AAA1 2017 AAA1 2017 1CLR 输出样例 2017 1CLR 2017 1CLR 2017 AAA1 2016 1CLR 2016 AAA1 数据范围 n∈[1,3×105];y∈[1900,2020]. c∈ { 1CLR, AAA1, CVP2, E33V, ICM1, NIP5 }. （ c 只会是这些字符串之一）

Hint 有没有比 O(nlogn) 更快的排序？

思路分析

可以看到令人毛骨悚然的时间限制200ms，所以我们要使用比O(nlogn)还快的 桶排序，时间复杂度O(n)。由于此处数据类型比较少，按年份和会议名称分类一共才120×6=720种。 此处我们借用桶排序的思路，但由于数据类型很少，我们可以把每一种类型放在一个桶里，即使用720个桶。 最后遍历输出。

AC代码

#include<stdio.h> int data[130][7]={0}; int judge(char a); void trans(int a); int main() { int i,j,k,n; int year; char name[7]; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%s",&year,name); data[year-1900][judge(name[0])]+=1; } for(i=120;i>=0;i--) for(j=0;j<6;j++) for(k=0;k<data[i][j];k++) { printf("%d ",i+1900); trans(j); } } int judge(char a) { if(a=='1') return 0; if(a=='A') return 1; if(a=='C') return 2; if(a=='E') return 3; if(a=='I') return 4; if(a=='N') return 5; } void trans(int a) { if(a==0) { printf("1CLR\n"); return; } if(a==1) { printf("AAA1\n"); return; } if(a==2) { printf("CVP2\n"); return; } if(a==3) { printf("E33V\n"); return; } if(a==4) { printf("ICM1\n"); return; } if(a==5) { printf("NIP5\n"); return; } }

补充：真正的桶排序

把数据分到不同的有序桶里面，在桶内部使用快排，最后把所有的桶连起来。 桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。当然桶排序的空间复杂度为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。此外，桶排序是稳定的。