HDU 1425 sort(桶排序+哈希函数)

xiaoxiao2021-02-28  79

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; }

转载请注明原文地址: https://www.6miu.com/read-78156.html

最新回复(0)