e558 - 01583 - Digit Generator

🔗 前往 ZeroJudge 原題

題目描述

題目要求對於給定的正整數 N，找出其最小的 generator。一個數字 N 的 generator 是指一個數字 M，使得 M 的 digit-sum 等於 N。Digit-sum 定義為數字本身加上其所有位數數字的總和。如果 N 沒有 generator，則輸出 0。

解題思路

這題的解題思路是先預先計算出所有可能的 digit-sum 的最小 generator。由於 N 的範圍是 1 到 100000，因此我們可以遍歷所有可能的數字 i (0 到 100000)，計算其 digit-sum，並將其儲存在一個陣列中。如果 digit-sum 尚未被計算過，則將 i 儲存為該 digit-sum 的最小 generator。 在預處理完畢後，對於每個輸入的 N，我們直接從陣列中查詢其最小 generator，並輸出結果。

複雜度分析

• 時間複雜度: O(N + Q)，其中 N 是預處理陣列的大小 (100001)，Q 是查詢次數。預處理需要遍歷 0 到 100000，計算每個數字的 digit-sum，這部分的時間複雜度是 O(N)。查詢部分的時間複雜度是 O(1)，因此總時間複雜度是 O(N + Q)。
• 空間複雜度: O(N)，因為我們需要一個大小為 100001 的陣列來儲存預處理結果。

程式碼

#include <iostream>
using namespace std;
int a[100001];
int main(){
	for(int i=0;i<=100000;++i){
		int tmp=i,all=0;
		all+=i;
		while(tmp>0){
			all+=tmp%10;
			tmp/=10;
		}
		if(a[all]==0)a[all]=i;
	}	
	int n;
	cin >> n;
	while(cin >> n)
		cout << a[n] << "\n";
}