2023天梯赛校内选拔赛 7-5 最小数-爱代码爱编程
题目：
给你一个数 n，现在小G想知道是否存在一个每位各不相同的值之和等于 n 的数，如果存在，则输出满足条件且值最小的数，否则输出 −1。
输入格式：
第一行，输入一个整数 t， 表示有 t 组数据。(1≤t≤45)
接下来每一行输入一个整数 n。(1≤n≤45)
输出格式：
输出 t 行，每行输出一个整数。
输入样例：
4
20
18
10
1输出样例：
389
189
19
1样例解释：
第一个样例，389 每位的值之和为 3+8+9=20，且这个数是在所有满足条件的数当中的最小值。
第二个样例，189 每位的值之和为 1+8+9=18，且这个数是在所有满足条件的数当中的最小值。
代码长度限制16 KB
Python (python3)
时间限制800 ms
内存限制128 MB
Java (javac)
时间限制800 ms
内存限制128 MB
其他编译器
时间限制400 ms
内存限制64 MB
思路：
这个题一上手最先想到的应该就是穷举法了，从1开始穷举直到找到满足条件的数字，我一开始就是这样想的，代码如下：
#include <stdio.h>
#include <math.h>
int number(int n)
{
int item = 0;
for (int i = 1; ; i++)
{
int sum = 0;
int hash[10] = { 0 };
int temp = i;
while (temp > 0)
{
item = temp % 10;
sum += item;
hash[item]++;
temp /= 10;
}
if (sum != n)
{
continue;
}
else
{
int cnt = -1;
for (int j = 0; j < 10; j++)
{
if (hash[j] <= 1)
{
cnt++;
}
}
if (cnt == 9)
{
return i;
}
}
}
return -1;
}
int main()
{
int t;
scanf("%d", &t);
int num;
for (int i = 0; i < t; i++)
{
scanf("%d", &num);
printf("%d\n", number(num));
}
return 0;
}但这个题目你穷举一定会超时，这时就应该转变思路。
题目输入20，要找一个每位各不相同且所有位的值加起来的结果等于20的数，既然要各不相同，不妨将20先减去9得11，这个9就应该是结果的个位，再将11减去8得3，这个8就是结果的十位，但这里要注意，3减去7为负数，我们需要找到一个条件，去判断前面减法的结果是否为结果的倒数第二高位，这里定义输入的20为n，结果的每一位数为i，为避免改变n造成麻烦，我们int num = n; 显而易见这个判断条件就是num - i < 0，num - i起到一个“预知”的功能，他能预知下一次减法的结果是否小于0，一旦小于0说明减完了，就应当保存num，即前面的3。
代码：
#include <stdio.h>
#include <math.h>
int number(int n)
{
if (n < 9)
{
return n;
}
int i = 9, j = 0;
int num = n;
int a[10] = { 0 };
while (num > 0)
{
num -= i;
a[j++] = i;
if (num - i < 0)
{
a[j++] = num;
break;
}
i--;
}
int s = 0;
for (int i = j; i >= 0; i--)
{
s = s * 10 + a[i];
}
return s;
}
int main()
{
int t;
scanf("%d", &t);
int num;
for (int i = 0; i < t; i++)
{
scanf("%d", &num);
printf("%d\n", number(num));
}
return 0;
}新算法完美通过了这道题
