hdu 1425 sort（最简单的hash）

sort

Time Limit: 6000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 12363    Accepted Submission(s): 3366

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

        我第一次用hash的题，最简单的哈希，空间换时间！！！ 156MS

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

代码：

#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;

#define N 1000001
bool hash[N];

inline bool scan_d(int &num)  //加速输入外挂！！！
{
    char in;
    bool IsN = false;

    in = getchar();
    if(in == EOF) return false;

    while(in!='-' && (in<'0'||in>'9')) in = getchar();

    if(in == '-') {IsN = true; num = 0;}
    else num = in-'0';

    while(in = getchar(), in>='0'&&in<='9')
    {
        num *= 10, num += in-'0';
    }
    if(IsN) num = -num;
    return true;
}

int main()
{
    int n, m, i, x, k;
    while(scanf("%d %d", &n, &m) != EOF)
    {
        memset(hash, false, sizeof(hash));
        for(i = 0; i < n; i++)
        {
            scan_d(x);
            hash[x+500000] = true;
        }
        k = 0;
        for(i = N-1; k != m; i--)
        {
            if(hash[i])
            {
                if(k++) printf(" ");
                printf("%d", i-500000);
            }
        }
        printf("\n");
    }

    return 0;
}