题目数据量达到了10^6,所以常规的sort排序什么的都会爆超时,
注意数据特点,是在一个特定的数据范围内的,所以我们可以用一个O(n)的桶排序,
然后构造一个最简单的哈希函数,每个值都加上数据范围的最大值,将桶排序用的数组开大一倍就好啦;
#include <iostream> #include <cstring> #include <stack> #include <cstdio> #include <cmath> #include <queue> #include <algorithm> #include <vector> #include <set> #include <map> #include<string> const double eps=1e-8; const double PI=acos(-1.0); using namespace std; int a[1000005]; int b[1000005]; int main() { int n,m; while(~scanf("%d %d",&n,&m)) { int tp; for(int i=0; i<n; i++) { scanf("%d",&tp); tp+=500000; a[tp]++; } int flag=0; int cou=0; for(int i=1000000; i>=0; i--) { if(cou==m) break; if(a[i]) { if(flag++) printf(" %d",i-500000); else printf("%d",i-500000); cou++; } } printf("\n"); } return 0; }