HDU 3183 A Magic Lamp

题目链接~~>

做题感悟：开始做这题时用了类似动态规划的方法做的，但是后来学习了RMQ算法后，听说可以用它来做，但是这题纠结了很久，就因为取整没处理好。

解题思路：假设数字长度为n，要求删去m个。可以理解为从n个中选n-m 个组成最小的数。那么第一个选入的最小的数一定在 1~m+1 个中选取，假设你在m+2个之后选取那么从m+2 到n 不足n-m个数，如果从1 ~ x（ x <= m ）,有可能前几位都很大就会成为被删的对象。所以第一个选入的最小数一定在1~m+1 中选。假设在1~m+1 中选取了x位置的数，那么下一次选取就要从x+1 ~ m+2 ，现在相当于从n-x 个数中删除m-x+1 个数，再用上面的方法选第二个数要从x+1~m+2 中选，以此类推……

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int MX = 1005 ;
     
    
   

    

     

    
    

     

      int n ;
     
    
   

    

     

    
    

     

      char s[MX],sx[MX] ;
     
    
   

    

     

    
    

     

      int m[MX][22] ;
     
    
   

    

     

    
    

     

      int min(int x,int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 return  s[x] <= s[y] ?  x : y ; // 注意 <=
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void pret(int len)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int i=1 ;i<=len ;i++)
     
    
   

    

     

    
    

     

       m[i][0]=i-1 ;
     
    
   

    

     

    
    

     
 for(int j=1 ;j!=20 ;j++)
     
    
   

    

     

    
    

     
 for(int i=1 ;i+(1<<j)-1<=len ;i++)
     
    
   

    

     

    
    

     

       m[i][j]=min(m[i][j-1],m[i+(1<<(j-1))][j-1]) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int query(int x,int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int k=(int)(log(y-x+1.0)/log(2.0)) ; //因为取整后面没加上（）错了n次
     
    
   

    

     

    
    

     
 return  min(m[x][k],m[y-(1<<k)+1][k]) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 while(~scanf("%s%d",s,&n))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int len=strlen(s) ;
     
    
   

    

     

    
    

     

       pret(len) ;
     
    
   

    

     

    
    

     
 int x=1,r=0 ;
     
    
   

    

     

    
    

     
 int p=len-n ;
     
    
   

    

     

    
    

     
 while(p--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int y=query(x,len-p) ;
     
    
   

    

     

    
    

     

       sx[r++]=s[y] ;
     
    
   

    

     

    
    

     

       x=y+2 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int i ;
     
    
   

    

     

    
    

     
 for(i=0 ;i<r ;i++) // 去掉前导零
     
    
   

    

     

    
    

     
 if(sx[i]!='0')
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     
 if(i==r)
     
    
   

    

     

    
    

     
 printf("0\n") ;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for( ;i<r ;i++)
     
    
   

    

     

    
    

     
 printf("%c",sx[i]) ;
     
    
   

    

     

    
    

     
 printf("\n") ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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