【題解】Zerojudge c431 - Sort ! Sort ! Sort !

題目連結

題目大意

給定 $n$ 個範圍為 $1 \sim 100$ 的正整數，要求由小到大排序後的結果。記憶體只有 $5$ MB。

題解

由於本題記憶體限制只有 $8$ MB，開長度為 $n$ 的陣列勢必是要吃 MLE 的。觀察到數字的大小為 $1 \sim 100$，我們只需要開大小為 $100$ 的陣列，紀錄每個數字出現的次數即可。這個排序的演算法叫做 Counting Sort，有興趣的可以上網搜尋相關的應用。

#include <stdio.h>

const int N = 101;

int main() {
	int n;
	scanf("%d", &n);
	int a[N] = {};
	for(int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		a[x]++;
	}
	for(int i = 0; i < N; i++) {
		while(a[i]--) {
			printf("%d ", i);
		}
	}
	puts("");
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge c431 - Sort ! Sort ! Sort !