hdu6351 Beautiful Now 全排列+剪枝（暴力） 2018杭电第五场B题

题意：给你一个不超过10^9的数n，和一个k；

有一种操作方式交换这个数的某一位与另一位进行交换 比如 201 可以换成 102，让你进行k次操作，求出交换后最大的数字和最小的数字.

要点：1 . 某一位的数字可以和它本身进行交换

           2 .交换的数字不可以有前导零（即第一位不可以是0）

题解：如果这个数字是n位数，那么其交换不超过n-1次就可以变成最大值和最小值，可以根据这个点进行剪枝，题目给的数字不超过10^9，那么进行全排列直接暴力就好了，时间复杂度最多10！，这道题给的时间限制为2500ms，跑一次暴力大概2000多ms，弱鸡的我不会贪心。

题目地址

#include<bits/stdc++.h>
using namespace std;

int maxx, minn, k, len;
int c[20], sum1[20], sum2[20], p[20];
char ss[20];

void update() {
    if(c[p[1]] == 0){
        return;
    }
    for(int i = 1; i <= len; i++){
        sum1[i] = p[i];
    }
    int kk = 0, s = 0;
    for(int i = 1; i <= len; i++){
        s = s * 10 + c[p[i]];
        if(sum1[i] != i){
            for(int j = i+1; j <= len; j++){
                if(sum1[j] == i){
                    swap(sum1[i], sum1[j]);
                    kk++;
                    if(kk > k) return;
                    break;
                }
            }
        }
    }
    if(kk > k){
        return ;
    }
    maxx = max(maxx, s);
    minn = min(minn, s);
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        memset(sum1,0,sizeof(sum1));
        memset(sum2,0,sizeof(sum2));
        scanf("%s%d",ss,&k);
        len = strlen(ss);
        for(int i = 0; i < len; i++) {
            c[i+1] = ss[i] - '0';
            sum1[c[i+1]]++;
            sum2[c[i+1]]++;
        }
        if(k >= len-1) {//剪枝 
            for(int i = 1; i <= 9; i++) {
                if(sum1[i]) {
                    printf("%d",i);
                    sum1[i]--;
                    break;
                }
            }
            for(int i = 0; i <= 9; i++) {
                while(sum1[i]) {
                    printf("%d",i);
                    sum1[i]--;
                }
            }
            printf(" ");
            for(int i = 9; i >= 0; i--) {
                while(sum2[i]) {
                    printf("%d",i);
                    sum2[i]--;
                }
            }
            printf("\n");
            continue;
        }
        for(int i = 1; i <= len; i++){
            p[i] = i;
        }
        minn = 2e9, maxx = -1;
        do{
            update();
        }while(next_permutation(p+1,p+len+1));//全排列 
        printf("%d %d\n",minn, maxx);
    }
    return 0;
}