f282 - 松鼠的願望
題目描述
題目要求讀取一系列整數，這些整數代表堅果的大小。松鼠只喜歡吃已經排序好的堅果，因此需要將讀取的堅果按照從小到大的順序輸出。
解題思路
這題可以使用計數排序 (Counting Sort) 來解決。由於堅果的大小範圍有限 (0 < n <= 100)，我們可以建立一個大小為 101 的陣列 a，用於記錄每個大小的堅果數量。然後，遍歷陣列 a，按照大小順序輸出對應數量的堅果。
程式碼中使用了 getchar_unlocked() 和 putchar_unlocked() 進行輸入輸出優化，以提高程式執行效率。read() 和 write() 函數分別用於快速讀取和輸出整數。
複雜度分析
- 時間複雜度: O(N + K)，其中 N 是輸入的堅果數量，K 是堅果大小的範圍 (100)。
- 空間複雜度: O(K)，其中 K 是堅果大小的範圍 (100)。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
int a[101],b,s;
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
while(b=read())
++a[b];
for(int i=1;i<101;++i){
while(a[i]--){
if(s)putchar_unlocked(' ');
write(i);
s=1;
}
}
}