HDU6351 BeautifulNow

ACM-ICPC

Publish Date: 2021-01-15

题目大意：

给你一个数，你可以交换这个数任意两位，可以交换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;
}