题目大意：
给你一个数，你可以交换这个数任意两位，可以交换k次。但是不能出现前导0。求经过k次操作可以形成的最大值和最小值。这个数小于20位。
解题思路:
首先，需要先解决这样一个问题：给定一个原序列，再给出它经过几次变换的序列，能不能求出， 原序列最少经过了几次交换，成为了新的序列。 不妨假设原序列的为 1，2，3….n。(如果是其他情况，完全可以建一个下标数组b，让它记录这一位现在是原来数组的第几位数) 假设交换了2号位和3号位,那么让b[2]=3，b[3]=2。又交换了3号位和5号位。那么就有b[5]=2,b[3]=5。至于怎么看交换了几次，我们可以看b[i]是不是i，如果不是，就说明这一位已经被交换了，那么就去查看b[i]，看这一位被换成了谁，就可以一直查询下去了。 具体怎么做呢，建立vis数组，表示第 i 是否被查询过，每次遇到b[i]不等于 i 的时候，就去继续查询b[i]位。
inline bool check(int n)
{//num数组即为下标数组
memset(vis,0,sizeof(vis));
int tot=0;
for(int i=1;i<=n;++i){
if(vis[i]) continue;//这一位数已经被计算过了
int tmp=0;
while(vis[i]==0){
++tmp;//记录有几个数被换过了
vis[i]=1;
i=num[i];
}
tot+=tmp-1;//tmp个数被换了，只需交换tmp-1次
//一个数被换了，说明没有被换
if(tot > k) return false;
}
return true;
}
解决了上述问题，那么就好办了，因为最多20位，所以可以直接全排列每一位，判断是否可在k次交换以内完成，然后计算其大小，统计答案即可。 而algorith库已经给我们提供了一个全排列函数，next_permutation，它会检测是否可进行下一次排序(从升序到降序，如果可以，则会把数组变到下一个排列，并返回true，如果不能，则直接返回false)，于之类似的有prev_permutation，它是从降序到升序。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
char s[21];
int T,k,num[21],vis[21];
inline bool check(int n)
{
memset(vis,0,sizeof(vis));
int tot=0;
for(int i=1;i<=n;++i){
if(vis[i]) continue;
int tmp=0;
while(vis[i]==0){
++tmp;
vis[i]=1;
i=num[i];
}
tot+=tmp-1;
if(tot > k) return false;
}
return true;
}
int main()
{
scanf("%d",&T);
while(T--){
scanf("%s%d",s+1,&k);
int n=strlen(s+1);
for(int i=1;i<=n;++i)
num[i]=i;//创建下标数组
int maxnum=0,minnum=1e9+5;
do{
if(s[num[1]]!='0'&&check(n)){
int sum=0;
for(int i=1;i<=n;++i)//计算序列的值
sum=sum*10+s[num[i]]-'0';//注意，这里是用交换下表数组，来代替交换原本的字符数组
if(sum<minnum) minnum=sum;
if(sum>maxnum) maxnum=sum;
}
}while(next_permutation(num+1,num+1+n));//这个函数就是这么用的
printf("%d %d\n",minnum,maxnum);
}
return 0;
}
最后送大家一个可爱的安柏
每日中二
有了自己的信仰，孤独就不再可怕。
