本文共 2126 字，大约阅读时间需要 7 分钟。

题目大意：

给你一个数，你可以交换这个数任意两位，可以交换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
   
    #include
    
     #include
     
      #include
      
       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
       
        maxnum) maxnum=sum;            }        }while(next_permutation(num+1,num+1+n));//这个函数就是这么用的        printf("%d %d\n",minnum,maxnum);    }    return 0;}
       
      
     
    
   

最后送大家一个可爱的安柏~~~~~

每日中二

有了自己的信仰，孤独就不再可怕。

转载地址：http://quuci.baihongyu.com/