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

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

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