数据交换

来源

2018杭电多校第五场

题意

给你一个正整数 ，你可以把 的第 位数字与第 位数字进行交换，，请注意题目允许自己和自己交换)，但是交换过程中不能出现前导零，(例如：11011，第1位和第3位不能交换，因为交换后会出现前导零，输入中保证没有前导零)。现在请你算出经过 次交换后可以得到的最小的整数和最大的整数。

思路

直接利用next_permutation算法进行枚举，复杂度是 ，更新每次的最大值和最小值，由于，这个计算量还是很大，要通过交换的次数是否超过 剪枝，又通过直接判定 再剪枝。

WA点

杭电C++会T，G++就能过，什么神仙编译器。。。。
特别注意前导0的存在。
数组尽量开小点，bool int也可以稍微加速。

另一种思路

对于每一位，搜索后面的数的最大值/最小值是否有大于/小于自己的，有就交换，这样理论复杂度只有 ，但是总代码量其实差不多。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;

const int maxn = 10;
bool vis[maxn];
int bit[maxn], id[maxn];
char s[maxn];

int k, len;

inline bool check() {
    memset(vis,0,sizeof(vis));
    int cnt=0;
    for(int i=0;i<len;i++) {
        if(!vis[i]) {
            int t=-1;
            while(!vis[i]) {
                t++;
                vis[i]=1;
                i=id[i];
            }
            cnt+=t;
            if(cnt>k) return false;
        }
    }
    return true;
}

int cmp(int a, int b) {
    return a>b;
}

int main() {
    int t; scanf("%d",&t);
    while(t--) {
        scanf("%s",s);
        scanf("%d",&k);
        len=strlen(s);
        for(int i=0;i<len;i++) {
            bit[i]=s[i]-'0';
            id[i]=i;
        }

        if(k>=len) {
            sort(bit,bit+len);
            int pos=0; while(bit[pos]==0) pos++;
            if(bit[0]==0) swap(bit[0],bit[pos]);
            for(int i=0;i<len;i++) printf("%d",bit[i]); printf(" "); 
            sort(bit,bit+len,cmp);
            for(int i=0;i<len;i++) printf("%d",bit[i]); printf("\n");
            continue;
        }

        int mi=2e9, mx=-1;
        do {
            if(bit[id[0]] && check()) {
                int temp=0;
                for(int i=0;i<len;i++) {
                    temp=temp*10+bit[id[i]];
                }
                mi=min(mi,temp);
                mx=max(mx,temp);
            }
        } while(next_permutation(id,id+len));
        printf("%d %d\n",mi,mx);
    }
}