HDU 1425 sort 重温

Description

n个不同整数，从大到小输出前m个

数字多达百万，sort定然超时

我们在数轴上将输入的n个数字标记，从后向前遍历输出即可

这样省去了sort的时间，只要遍历的时间

Code

#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

//int main()
//{
//    int n, m, tem;
//    while(~scanf("%d%d", &n, &m))
//    {
//        map<int, bool> mp;
//        for(int i = 0; i < n; ++i)
//        {
//            scanf("%d", &tem);
//            mp[tem] = 1;
//        }
//        int cnt = 0;
//        for(int i = 500000; i >= -500000 && cnt < m; --i)
//            if(mp[i])
//            {
//                cout << i << ' ';
//                cnt++;
//            }
//        cout << '\n';
//    }
//    return 0;
//}

bool has[1000009];

int main()
{
    int n, m, tem;
    while(~scanf("%d%d", &n, &m))
    {
        memset(has, 0, sizeof(has));
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &tem);
            has[tem + 500000] = 1;
        }
        int cnt = 0;
        for(int i = 1000000; i >= 0 && cnt < m; --i)
            if(has[i])
            {
                printf("%d%c", i - 500000,cnt == m - 1 ? '\n' : ' ');
                cnt++;
            }
    }
    return 0;
}

如上，我试过map，他不用坐标偏移，但更为耗时，毕竟使用哈希目的在于节约时间，所以哈希不要用map