e973 - 3. 滿意度調查 (Survey of Satisfaction)
題目描述
題目要求讀取一個數字字串，統計字串中每個數字 (0-9) 出現的次數，然後按照出現次數從大到小排序輸出這些數字。如果出現次數相同，則按照數字大小排序輸出。
解題思路
程式首先建立一個大小為 10 的整數陣列 b，用於儲存每個數字 (0-9) 的出現次數。然後，程式讀取輸入字串，並統計每個數字的出現次數。接著，程式進入一個迴圈，每次找到出現次數最多的數字，並將其輸出，然後將該數字的出現次數設為 0。這個過程重複進行，直到所有數字的出現次數都為 0。
複雜度分析
- 時間複雜度: O(N + K log K)，其中 N 是輸入字串的長度，K 是不同數字的數量 (最多為 10)。統計出現次數需要 O(N) 的時間，排序需要 O(K log K) 的時間。
- 空間複雜度: O(1)，因為程式只使用了一個大小為 10 的固定大小的陣列來儲存數字的出現次數。
程式碼
#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 b[10],mx,i;
char a;
int main(){
while(a=getchar_unlocked()){
if(a==-1)break;
++b[a-48];
}
do{
for(i=9,mx=0;i>=0;--i)
b[i]>mx&&(mx=b[i]);
if(!mx)break;
for(;i<10;++i){
if(b[i]==mx){
putchar_unlocked(i+48);
putchar_unlocked(' ');
b[i]=0;
break;
}
}
}while(1);
}