e590 - 11371 - Number Theory for Newbies
題目描述
題目要求對於給定的正整數，重新排列其數字以形成兩個整數 a 和 b，使得 a - b 的值最大，且 a - b 必須是 9 的倍數。輸出格式為 "a - b = a-b = 9 * x"。
解題思路
解題思路是將輸入數字的各位數字進行排序。為了使 a - b 最大，我們需要將數字按降序排列得到 a，並將數字按升序排列得到 b。然後計算 a - b，並將結果除以 9 得到 x。由於題目保證 a - b 總是 9 的倍數，因此除法結果一定為整數。程式碼中，s[i] 陣列用於統計每個數字出現的次數。然後，程式碼按照數字大小從 9 到 0 的順序，將數字輸出到 a 中，輸出次數等於該數字在原始數字中出現的次數。接著，程式碼按照數字大小從 1 到 9 的順序，將數字輸出到 b 中，如果數字為 0，則將其放在最後輸出。最後計算 a - b 並輸出結果。
複雜度分析
- 時間複雜度: O(n log n)，其中 n 是輸入數字的位數。主要時間花費在排序上，但這裡實際上是統計數字出現次數，然後按照次數輸出，所以可以視為 O(n)。
- 空間複雜度: O(1)，因為我們只使用了一個固定大小的陣列
s來儲存數字的計數，其大小為 10。
程式碼
#include <stdio.h>
char a[12];
int main(){
long long int x,y;
int s[10],it;
while(scanf("%s",&a)>0){
x=0;y=0;it=0;
for(int i=0;i<10;++i)
s[i]=0;
while(a[it]>='0'){
++s[a[it]-48];
++it;
}
for(int i=9;i>=0;--i){
int t=s[i];
while(t>0){
t--;
x*=10;
x+=i;
putchar_unlocked(i+48);
}
}
printf(" - ");
for(int i=1;i<10;++i){
if(s[i]){
while(s[i]-->0){
y*=10;
y+=i;
putchar_unlocked(i+48);
}
break;
}
}
while(s[0]-->0){
y*=10;
putchar_unlocked('0');
}
for(int i=2;i<10;++i){
while(s[i]-->0){
y*=10;
y+=i;
putchar_unlocked(i+48);
}
}
x-=y;
printf(" = %lld = 9 * %lld \n",x,x/9);
}
}