Digits swap
题目 Digits swap
方法
从最后的结果开始倒推 如果想要数更大那么首先是需要让前面的数更大
当时考试的时候想到的是先把所有的数排个序 然后从左往右看还有多少个需要交换
这个时候需要注意的是比如样例
1854268 3
这里1有两个8可以换所以就想到直接每次换最右边的 有50多分
想了很久都没有想到哪错了 然后在able的数据87990 2 发现不能简单的直接找最右边的
需要将比如87990 最大的情况是 99870要把所有的9在的前两位和能够交换的9进行排序
写了之后发现还是没过完有84分
当时想到能够最左边进行交换时验证了样例
- [1]85426[8] into 8854261.
- 88[5][4]261 into 8845261
- 88[4]52[6]1 into 8865241
第二步的时候先交换 6和4再交换54对结果没影响而且也不会产生多余的次数
但是下面这个例子875699 4 按照上面的方法最终结果998756
然后真正的答案过程应该是
975698 995678 998675 998765
所以在找前面两个78交换位置的时候需要枚举所有情况这里没有多想了 直接写了dfs
/*
87990 2
6879990 2
9876 2
875699 4
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
char s[20];
int n;
int swap_times;
int d[20];
bool cmp(int a, int b)
{return a>b;
}
LL ans;
LL tmp_ans;
void dfs(int pos, int times)
{if(pos==n-1 || !times) {//注意这里要用long longtmp_ans = atoll(s);ans = max(ans, tmp_ans);return ;}int x = d[pos];if(s[pos] - '0' == x) dfs(pos+1, times);else {for(int i=pos+1; i<n; i++)if(s[i] - '0' != d[i] && s[i] - '0' ==x) {swap(s[i], s[pos]);dfs(pos+1, times-1);// 这里还可以比较大小剪枝swap(s[i], s[pos]);}}
}
int main()
{
// freopen("swap.in", "r",stdin);scanf("%s", s);n = strlen(s);
// int num = atoi(s);
// printf("%d\n", num);for(int i=0; i<n; i++) d[i] = s[i] - '0';scanf("%d", &swap_times);sort(d, d+n, cmp);dfs(0, swap_times);cout<<ans;return 0;
}
