A25785. 给定一个正整数n，请将n中的每位数字重新排列并组成一个新数，要求新数的值要小于n，请找出所有符合要求的新数中最大的那个正整数，如果不存在这样的正整数，则输出-1。例1：n=312，312中每位上的数字依次是3、1、2，重新排列组成的新数有321、231、213、132、123，新数中小于312的有231、213、132、123，其中符合要求的最大正整数是231；例2：n=123，123中每位上的…
填空题
中等
知识点
题目描述
给定一个正整数n，请将n中的每位数字重新排列并组成一个新数，要求新数的值要小于n，请找出所有符合要求的新数中最大的那个正整数，如果不存在这样的正整数，则输出-1。
例1：n=312，312中每位上的数字依次是3、1、2，重新排列组成的新数有321、231、213、132、123，新数中小于312的有231、213、132、123，其中符合要求的最大正整数是231；
例2：n=123，123中每位上的数字依次是1、2、3，重新排列组成的新数有312、321、231、213、132，新数中不存在小于123的正整数，故输出-1。
输入描述
输入一个正整数 n (1≤ n <2的63次方)
输出描述
输出一个正整数，表示符合要求的最大正整数
样例输入
312样例输出
231参考答案
#include <bits/stdc++.h>
using namespace std;
long long n, m;
int a[22], k, t[22], ans[22];
bool sign = true;
void DFS(int step) {
if (!sign)
return;
if (step > k) {
int x = 0;
for (int i = 1; i <= k; i++)
x = x * 10 + ans[i];
// cout<<x<<endl;
if (x < n && sign) {
cout << x;
sign = false;
}
return;
}
for (int i = 1; i <= k; i++) {
if (t[i] == 0) {
ans[step] = a[i];
t[i] = 1;
DFS(step + 1);
t[i] = 0;
}
}
}
int main() {
cin >> n;
m = n;
while (m) {
t[m % 10]++;
m /= 10;
}
for (int i = 9; i >= 0; i--)
for (int j = 1; j <= t[i]; j++) {
a[++k] = i;
}
memset(t, 0, sizeof(t));
DFS(1);
if (sign)
cout << -1;
return 0;
}
上一题
下一题