HDOJ 1425 sort

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

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

版本一:(HASH版)

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

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
// HDOJ 1425
// Author: Tanky Woo
#include <iostream>
#include <algorithm>
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

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
// HDOJ 1425
// Author: Tanky Woo
#include <iostream>
#include <algorithm>
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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 1425 sort》有356个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注