题解 CF1462C 【Unique Number】
Griseo_nya
2021-02-01 14:50:44
这道题的题目很明显的告诉了我们要贪心
。
首先，题目要求我们“找出符合条件的最小数”，而这道题中各个数位填什么对下一位填的数几乎没有关系（除了你不能再用这个数），故知道我们可以用贪心的方法来解决这道题。
那么下面就该想：怎么贪心呢？
明显在 $x<10$ 时直接输出 $x$ 就可以，因为多位明显是会比一位的数大的。
因为题目要求我们各位数字不能重复，所以我们能取到的最大的 $x$ 就是 $0+1+2+3+4+5+6+7+8+9=45 $ 所以当 $x>45$ 时就无法取到，直接输出 $-1$ 即可。
其余的数我们可以用贪心的思路（前面说过了我们要这样啊）：
从大往小，依次从大往小填数，每次给 $x$ 减去本位要填的数，当本位应填的数大于 $x$ 时，就停止循环，并且输出每一位就ok啦☆
那么下面就是代码啦：
```cpp
#include <bits/stdc++.h>
using namespace std;
int t;
int main(){
cin>>t;
while(t--){
int x;
cin>>x;
if(x<10)cout<<x<<endl; //预处理 x<10 的情况
else if(x>45)cout<<-1<<endl; //预处理 x>45 的情况
else{
int i;
vector<int> a; //开一个 vector ，可以理解为动态数组
for(i=1;i<=9;i++){
int now=10-i; //当前应填的数字
if(now>=x){
cout<<x;
//x 即是我们当前应填的最高位，所以可以直接输出
reverse(a.begin(),a.end());
//因为我们是从后往前填的，所以要反转一下
for(int i=0;i<a.size();i++){
cout<<a[i]; //输出之前的每位数字
}
cout<<endl; //换行
break; //本次循环结束
}
else {
x-=now; //给剩余的 x 减去当位应填的数
a.push_back(now); //把这位数放进数组里
}
}
}
}
return 0;
}
```