526互联

Codeforces Round 690 (Div. 3) C. Unique Number

发布时间 2023-10-13 15:13:23作者: zsxuan

给一个正整数 \(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;
}