avatar
fireworks99
keep hungry keep foolish

HDU 1425 sort

Description

给你n个整数,请按从大到小的顺序输出其中前m大的数。

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1425

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

?看哈希碰到的题,刚刚了解了输入挂,就推荐给我。莫非被监视了?

用挂Code

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; int a[1000005]; int Scan() { int res = 0, ch, flag = 0; if( (ch = getchar() ) == '-')///括号搞清楚 flag = 1; else if(ch >= '0' && ch <= '9') res = ch - '0'; while( (ch = getchar()) >= '0' && ch <= '9')///= 与 == 分清 res = res * 10 + ch - '0'; return flag ? -res : res; } void Out(int a) { if(a < 0) { putchar('-'); a *= -1; } if(a > 9) Out(a / 10); putchar(a % 10 + '0'); } bool cmp(int a, int b) { return a > b; } int main() { int n, m; while(~scanf("%d%d", &n, &m)) { for(int i = 0; i < n; ++i) a[i] = Scan(); sort(a, a + n, cmp); for(int i = 0; i < m; ++i) { Out(a[i]); printf("%c", i == m - 1 ? '\n' : ' '); } } return 0; }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53

emmm…用C++TLE了,用G++勉强过

en

hash?(空间换时间)

#include <cstdio> #include <iostream> using namespace std; int hash1[1000005]; int main() { int n, m; while(~scanf("%d%d", &n, &m)) { while(n--) { int t; scanf("%d",&t); hash1[t + 500000]++; } for(int i = 500000 * 2; i >= 0; i--) { if(hash1[i] != 0) { m--; printf("%d%c", i - 500000, m == 0 ? '\n' : ' '); if(m == 0) break; } } } return 0; }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
Site by Baole Zhao | Powered by Hexo | theme PreciousJoy