ACdream 1417 Numbers

题目链接~~>

做题感悟：比赛的时候用的广搜，然后高高兴兴的写完果断TLE ，做题的时候无论什么题都要用笔画一下，模拟几组数据，这样也许就AC了（做题经验，有心者谨记！）。

解题思路：贪心/规律

          这题如果暴力找倍数的话必定超时（如果不超时就是数据问题了），但是我们可以把它的倍数分类，把位数相同的倍数放在一类里，这样一共才18类，分类后只需要找这一类中最小的元素代表这一类就可以了。问题就转化到怎样找某一定位数某个数的字典序最小的倍数，我们知道最小字典序的那个数最前面如果最小的话只能放1后面尽可能放 0 ，这样可以使达到的倍数尽量小。
          这里假设 k 的 6 位的倍数是 100xyz（这个数是超过 100000 的第一个倍数），那么这个数是否是最小的呢？我们让 100xyz 再加上 k (这里假设加上 k 之后位数不超 6 位)，假设得到 100wpq，那么这个数的字典序一定比 100xyz的字典序大，由这个我们也可以知道 100xyz 一直加 k 得到的位数为 6 位的数的倍数一定都比 100xyz字典序大，这样我们可以得到答案的解，就是枚举超过 10，100 ，1000 ，10000 ……10^18 的第一个 k 的倍数取字典序最小的一个。

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<bitset>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<cctype>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std  ;
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      #define L(x) (x * 2)
     
    
   

    

     

    
    

     

      #define R(x) (x * 2 + 1)
     
    
   

    

     

    
    

     

      const int INF = 0x3f3f3f3f ;
     
    
   

    

     

    
    

     

      const double esp = 0.0000000001 ;
     
    
   

    

     

    
    

     

      const double PI = acos(-1.0) ;
     
    
   

    

     

    
    

     

      const INT mod =  10000007 ;
     
    
   

    

     

    
    

     

      const int MY = 1400 + 5 ;
     
    
   

    

     

    
    

     

      const int MX = 18 + 5 ;
     
    
   

    

     

    
    

     

      char ans[MX] ,str[MX] ;
     
    
   

    

     

    
    

     

      INT n ,k ;
     
    
   

    

     

    
    

     

      int judge(int x)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int ans = 0 ;
     
    
   

    

     

    
    

     
 while(x)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       x /= 10 ;
     
    
   

    

     

    
    

     

       ans++ ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return ans ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 while(scanf("%I64d%I64d" ,&n ,&k) ,n+k)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 sprintf(ans ,"%lld" ,k) ;
     
    
   

    

     

    
    

     
 int m = judge(k) ;
     
    
   

    

     

    
    

     
 for(int i = m ;i <= 18 ; ++i)  // 枚举每一种
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       INT temp = pow(10 ,i) ;
     
    
   

    

     

    
    

     
 if(temp > n)  break ;
     
    
   

    

     

    
    

     
 if(temp % k == 0)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 sprintf(str ,"%lld" ,temp) ;
     
    
   

    

     

    
    

     
 if(strcmp(ans ,str) > 0)
     
    
   

    

     

    
    

     
 strcpy(ans ,str) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       INT tx = (temp/k+1)*k ;
     
    
   

    

     

    
    

     
 if(tx > n)  continue ;
     
    
   

    

     

    
    

     
 sprintf(str ,"%lld" ,tx) ;
     
    
   

    

     

    
    

     
 if(strcmp(ans ,str) > 0)
     
    
   

    

     

    
    

     
 strcpy(ans ,str) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 cout<<ans<<endl ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/40212785