HDOJ 1425 sort

这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。

好吧，水题。但是要注意此题格式，最后一个数字后面不能有空格，先前多次PE了。

网上好多人用hash做的。空间换时间，我2个都做了，代码发下：

版本一：（HASH版）

内存：4112K 时间：328MS 代码长度：757B

// HDOJ 1425
// Author: Tanky Woo
#include 
#include 
using namespace std;

int hash[1000001];
int main()
{
    int n, m;
    int num; 
    while(scanf("%d %d", &n;, &m;) != EOF)
    {
        memset(hash, 0, sizeof(hash));
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &num;);
            hash[num+500000] = 1;
        }
        int cnt = 0;
        for(int i = 1000000; i >= 0; --i)
        {

            if(hash[i])
            {
                cnt++;
                if(cnt == m)
                    printf("%d\n", i-500000);
                else
                    printf("%d ", i-500000);
            }
            if(cnt == m)
                break;
        }
    }
    return 0;
}

版本二：（qsort版）

内存：2164K 时间：562MS 代码长度：610B

// HDOJ 1425
// Author: Tanky Woo
#include 
#include 
using namespace std;


long arr[1000000];
long n, m;


int compare(const void *e1, const void *e2)
{
    return -(*((long *)e1) - *((long *)e2));   // 
}

int main()
{
    while(scanf("%ld %ld", &n;, &m;) != EOF)
    {
        for(int i = 0; i < n; ++i)
            scanf("%d", &arr;[i]);
        qsort(arr, n, sizeof(arr[0]), compare);
        for(int i = 0; i < m; ++i)
        {
            if(i == m-1)
                printf("%d", arr[i]);
            else
                printf("%d ", arr[i]);
        }
        printf("\n");
    }
    return 0;
}