sort

Time Limit: 6000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 50513    Accepted Submission(s): 14316 Problem Description 给你n个整数，请按从大到小的顺序输出其中前m大的数。   Input 每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。   Output 对每组测试数据按从大到小的顺序输出前m大的数。   Sample Input 5 3 3 -35 92 213 -644   Sample Output 213 92 3 Hint 请用VC/VC++提交   Author LL   Source ACM暑期集训队练习赛（三）  

 题目数据量达到了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; }