<>

<转载于   >

题目大意：

给出一个长度不超过1000位的数，求删去m位数字以后形成的最小的数字是多少。

解题分析：

分析：我们可以把题目转化为这样一个模型：从A[1]、A[2]、……、A[n] n个数中选出n-m个数，使得组成的数最小。

一、使用RMQ，设原数字长为n，那么除去m个数字后还剩n-m个数字。    下面的(一)、(二)用到了抽屉原理

（1）因为有n-m个数字，那么在0到m-1位置中最小的那个数字必是结果中的第一个数字，记录其位置为pos

（2）然后从这个位置的下个位置pos+1开始到m+2位置的数字中最小的那个数字必定是结果中第二个数字，以此类推下去向后找。

（3）为了保证数字最小,所以要保证高位最小,还要保证数字长度满足条件。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6  7 const int M = 1e3+10; 8 char s[M]; 9 char ans[M];10 int st[M][20],m;11 int Min(int a,int b){    //根据它们在字符串中的值，返回值更小的元素的下标 12     return s[a]<=s[b]?a:b;13 }14 void RMQ_init(int len){     //用ST表预处理[i,i+2^J-1]这个区间内最小值所在的坐标 15     for(int i=0;i
        
       
      
     

 

 

2018-10-20