CodeForces - 95B（DFS） - JavaScript

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接 ：http://codeforces.com/problemset/problem/95/B

题目大意 ：给你一个正整数n (1 ≤ n ≤ 10 ¹⁰⁰⁰⁰⁰ )，求不大小于它的超级幸运数字（超级幸运数字就是只含有数字4和数字7，并且4和7的数目相同）

例：

Sample Input

4500

Sampule Output

4747

解题思路： 压根没想到用DFS，开始就想着，先判断数字的个数是否是个奇数，如果是个奇数就很好办，直接加一位数字，前一半是4后一半是7，当它的数字个数为偶数时就模拟从高位一个一个判断的，然后发现好复杂就放弃了。然后又想用全排列就变得很简单了，但是这数字太大了可能又10的5次方位，大一点的数肯定就算不出来了。看了大佬的代码才知道还可以用DFS。

如果数字个数是奇数的情况下可以直接输出，如果是偶数我们就用DFS从高位开始搜索，含有4个参数，第一个参数是当前搜索的位置，还要有一个参数判断数字是否已经比原来那个更大了，还有两个参数是分别用来记录当前4和7可用的个数，初始时4和7可用的个数都是原来数长度的一半。对于数的每一位我们只需要判断两种情况，是否<=4，如果=4继续搜索，如果小于4，直接变成4这时数就比原来更大了，后面还有的位就分别先填充可用的4，再填充可用的7，这用就能保证它最小了。如果大于4，就判断是否<=7就可以了，和小于4同理操作。然后还有一种情况就是，所有数字都大于7，这时候就要多加两个数位，前一半是4后一半是7就够了。

附上代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 char n[];

 char ans[];

 int len;

 bool dfs(int pos,int cnt4,int cnt7,bool toup)

 {

     if(pos==len) return true;  //一直搜索到数字的尾部也未退出，说明它本身就是超级幸运数字

     if(toup) //如果已经变大了就把没用用完的4和7填完，先填4再填7，返回

     {

         for(int i=;i<cnt4;i++)

             ans[pos++]='';

         for(int i=;i<cnt7;i++)

             ans[pos++]='';

         return true;

     }

     if(n[pos]<=''&&cnt4)

     {

         if(dfs(pos+,cnt4-,cnt7,n[pos]<''))

         {

             ans[pos]=''; //如果是<4将改为改成4

             return true;

         }

     }

     if(n[pos]<=''&&cnt7)

     {

         if(dfs(pos+,cnt4,cnt7-,n[pos]<''))

         {

             ans[pos]='';  //如果<7将该位改成7

             return true;

         }

     }

     return false;  //未搜索到大于原数的

 }

 int main()

 {

     while(cin>>n)

     {

         len=strlen(n);

         if(len%||!dfs(,len/,len/,false))  //如果数位是奇数，或者搜搜索到的，直接先填4再填7

         {

             int x=(len%?(len+)/:(len+)/);

             for(int i=;i<=x;i++)

                 cout<<;

             for(int i=;i<=x;i++)

                 cout<<;

             cout<<endl;

             continue;

         }

         cout<<ans<<endl;

     }

     return ;

 }