a561: 內存不足

2021-06-02 23:07:53 +0800 CST Tags: bitmask, counting-sort

出處：https://zerojudge.tw/ShowProblem?problemid=a561
提交：https://zerojudge.tw/Submissions?problemid=a561&account=allllllan123456

問題：給定 $n\in[1,10000000]$ 個不重複而且小於 10000000 的非負整數，求其排序後的結果 (只印 index 為 10 的倍數的元素)。

解法：就 counting sort。但這題之所以要強調「內存不足」是因為，他不希望你用來記錄個數的 array 是一般人常用的 int 型態，所以才限定這些數字都不重複，才能使用 bool 型態記錄有或無，如果是 C++ 可以很偷懶地使用 bitset，但如果是 C 語言的話就必須把 32 個 bit 壓在一個 int 裡面，網路上 (包括我自己) 也有寫出 C 語言的方法，很容易就可以找到程式碼。然後這題也要注意不要使用其他的輸入方式例如 cin、cout，因為這還需要其他 library 的協助極有可能會造成內存不足，結論就是 bitset 是個好用的玩意兒。

 1#include <bitset>
 2
 3int main() {
 4    std::bitset<10000000> table;
 5    int count=0, x, n; scanf("%d", &n);
 6    for (int i=0; i<n; i++)
 7        scanf("%d", &x), table[x] = true;
 8    for (int i=0; i<10000000; i++)
 9        if (table[i] && !((count++) % 10))
10            printf("%d ", i);
11    putchar('\n');
12    return 0;
13}