给一个正整数 \(x\) ，需要构造一个最小的正整数 \(n\) 使得 \(\sum digt(n) = x\) ，并且 \(\forall i \neq j, digt(n)_i \neq digt(n)_j\) 。
首先观察到 \(0\) 没有贡献，且会增加位数，所以不能有 \(0\) 。
由于每个数位只能出现一次，显然合法的 \(x\) 范围为 \([0, \sum_{i=1}^{9} i]\) ，又 \(x \geq 1\) 。于是合法范围为 \([1, 45]\) 。这个范围内的数一定可以被若干个数位组合。
需要构造最小的 \(n\) 需要考虑两个显然的条件：
- 位数尽可能少。
- 于是尽量使用更大的数字
- 位数相同的情况下高位权值尽可能小
- 于是更大的数字在更低位
于是从低位到高位用最大的数字贪心填充即可。
view
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
int n; std::cin >> n;
if (n > 45) std::cout << -1 << "\n";
else {
std::vector<int> ans;
int cur = 9;
while (n) {
while (n - cur < 0) cur -= 1;
n -= cur;
ans.push_back(cur);
cur -= 1;
}
std::reverse(ans.begin(), ans.end());
for (auto x : ans) std::cout << x;
std::cout << "\n";
}
}
int main() {
int _ = 1; std::cin >> _;
while (_--) {solve();}
return 0;
}