【6351 HDU】Beautiful Now（暴力）

向右看齐 2022-05-17 09:57 132阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6351][http_acm.hdu.edu.cn_showproblem.php_pid_6351]

题意：输入T组测试，每组测试样例输入一个数n和交换次数k，输出k次交换后能得到的最大数和最小数。

思路：利用全排列进行暴力操作。首先利用全排列可以得到所有的情况，然后找到交换k次的情况所得到的数跟最大数和最小数比较，然后更新最大数和最小数。然后接下来主要就是怎样判断交换了多少次。这里我们用flag数组标记下标，再用vis数组来标记我们要查询的数是否已经被判断过，然后我们需要用一个while循环来判断跟它交换的数是否又跟其他的数进行了交换，这样我们就知道了一共有几个数进行了交换，也就知道了一共交换了多少次，同时不要忘记把这些数的vis标记为1，表示这些数已经被访问过了。

My DaiMa：

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #define per(i,a,b) for(int i = a; i < b; i++)
    using namespace std;
    const int Max = 10000003;
    typedef long long ll;
    int a[15],flag[15],vis[15],len;//a数组存的是字符串中的每一位数，flag用来存下标，vis用来标记
    ll k;//输入的交换次数
    int Count()
    {
        fill(vis,vis+len,0);
        int c = 0;
        //for( int i = 0; i < len; i++)
        per(i,0,len)
        {
            if(vis[i] == 0)
            {
                int t = 0;
                while(vis[i] == 0)
                {
                    vis[i] = 1;//将访问过的数标记为1
                    t++;//t代表跟第i个数交换有关的数一共有几个
                    i = flag[i];//将下标指向跟它进行交换的数的下标，即判断跟它交换的数是否还与其他的数进行了交换
                }
                c += t-1;//用来记录交换次数
            }
            if(c > k) return 0;
    
        }
        return c;//返回交换次数
    }
    int main()
    {
        int t;
    
        char s[15];
        scanf("%d",&t);
        while( t-- )
        {
            scanf("%s %d",s,&k);//用字符串来存输入的数
            len = strlen(s);
            ll n = 0,mx,mn;
            //for(int i = 0; i < len; i++)
            per(i,0,len)
            {
                a[i] = s[i]-'0';
                flag[i] = i;
                n = n*10+a[i];
            }
            mx = mn = n;
            do
            {
                if(a[flag[0]] != 0 && Count() != 0)//要找交换k次的情况并且全排列所组合的这个数不能是前导0
                {
                    ll sum = 0;
                    //for(int i = 0; i < len; i++)
                    per(i,0,len)
                        sum = sum*10+a[flag[i]];
                    mx = max(mx,sum);//更新最大数
                    mn = min(mn,sum);//更新最小数
                }
    
            }while(next_permutation(flag,flag+len));//注意是下标全排列
            printf("%lld %lld\n",mn,mx);
        }
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_6351]: http://acm.hdu.edu.cn/showproblem.php?pid=6351