HDU 6351 Beautiful Now（DFS）多校题解-白红宇

HDU 6351 Beautiful Now（DFS）多校题解

阅读量：4882 次

发布时间：2019-06-11

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

思路：一开始对k没有理解好，题意说交换k次，如果我们不需要交换那么多，那么可以重复自己交换自己，那么k其实可以理解为最多交换k次。这道题dfs暴力就行，我们按照全排列最大最小去找每一位应该和后面哪一位交换。k = 0没判断好WA了2发...

如果k >= len - 1，那么最大最小就是直接sort非前导零的答案。如果k < len - 1，那么我们交换肯定从最大位数交换，比如现在求最大值，那么我们从第一位依次判断，如果该位不是他后面最大的，那么就和后面最大的交换（如果最大的有多个，那么就每个都搜索一下），否则不消耗交换次数判断下一位。最小同理

注意前导零。

代码：

#include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define ll long longusing namespace std;const int maxn = 100+10;const int INF = 0x3f3f3f3f;int bit[12];ll pos,k,Max,Min;ll MIN[12],MAX[12];ll get_num(int a[]){ ll ans = 0; for(int i = 1;i <= pos;i++){ ans = ans * 10 + a[i]; } return ans;}void dfs_max(int a[],int rt,int tim){ if(tim == k){ Max = max(Max,get_num(a)); return; } if(rt == pos){ Max = max(Max,get_num(a)); return; } if(a[rt] == MAX[rt]){ Max = max(Max,get_num(a)); dfs_max(a,rt + 1,tim); } else{ for(int i = rt + 1;i <= pos;i++){ if(a[i] != MAX[rt]) continue; swap(a[rt],a[i]); Max = max(Max,get_num(a)); dfs_max(a,rt + 1,tim + 1); swap(a[rt],a[i]); } }}void dfs_min(int a[],int rt,int tim){ if(tim == k){ Min = min(Min,get_num(a)); return; } if(rt == pos){ Min = min(Min,get_num(a)); return; } if(a[rt] == MIN[rt]){ Min = min(Min,get_num(a)); dfs_min(a,rt + 1,tim); } else{ for(int i = rt + 1;i <= pos;i++){ if(a[i] != MIN[rt]) continue; swap(a[rt],a[i]); Min = min(Min,get_num(a)); dfs_min(a,rt + 1,tim + 1); swap(a[rt],a[i]); } }}int main(){ int T; char n[12]; scanf("%d",&T); while(T--){ scanf("%s%d",n,&k); pos = strlen(n); for(int i = 0;i < pos;i++){ bit[i + 1] = n[i] - '0'; } for(int i = 1;i <= pos;i++){ MIN[i] = bit[i]; } sort(MIN + 1,MIN + pos + 1); for(int i = 1;i <= pos;i++){ MAX[i] = MIN[pos - i + 1]; } if(MIN[1] == 0){ int p = 2; while(MIN[p] == 0){ p++; } swap(MIN[1],MIN[p]); } Max = 0,Min = INF; k = min(k,pos - 1); dfs_max(bit,1,0); dfs_min(bit,1,0); printf("%lld %lld\n",Min,Max); } return 0;}

转载于:https://www.cnblogs.com/KirinSB/p/9488342.html

你可能感兴趣的文章