题目
题意：给出一个不含前前导零的字符串，要求删除m个字符（），使得该字符串数字值最小。
1、单调队列解法：反过来看删除m个字符，就是留下m'(len-m)个字符，根据巢鸽原理，选择区间的右区间的端点从len-m'+1（闭区间）开始依次后移 ，
而左区间为1或上次被选位置开始（开区间），从这m'个区间中选择最小数字，可得最小值。
因为右端点是逐渐后移，与滑动窗口很类似，所以可以使用单调递减队列维护区间最小值。
//#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll ;
#define int ll
#define mod 1000000007
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j) for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//int lcm(int a , int b){return a*b/gcd(a,b);}
//ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define cin(x) scanf("%lld" , &x);
#define endl '
'
const double esp = 1e-6;
const int N = 1e6+9;
const int maxn = 2e5+9;
char a[maxn];
char q[maxn] ;
int rear , front ;
int n , m ;
void solve(){
int len = strlen(a+1);
m = len - m ;
rear = front = 0 ;
vector<char>v;
rep(i , 1 , len){
while(rear != front && a[i] < q[rear]){
rear--;
}
q[++rear] = a[i];
if(i >= len-m+1){
v.pb(q[++front]);
}
}
while(size(v) && *v.begin() == '0') v.erase(v.begin());
if(size(v) == 0) cout << 0 << endl;
else{
for(auto i : v){
cout << i ;
}
cout << endl;
}
}
signed main()
{
//int _ ;cin>>_;while(_--)
while(~scanf("%s%lld" , a+1 , &m))
solve();
}
2.RMQ解法：同上也是求m个区间的最小值，只是不同的实现。
定义方程：(dp[i][j])表示起点为i长度为(2^j)的区间最小值
RMQ主要思想是倍增:比如预处理1-4区间的最小值可通过1-2和3-4的最小值得出。小区间推出大区间。
边界：(dp[i][0] = a[i])
递推:(dp[i][j] = min(dp[i][j-1] , dp[i+(1<<(j-1))][j-1]);(i+2^j-1 <= len))
查询操作：取长度(len = log_2(r-l+1)) , 结果为:(min(dp[l][len] , dp[r-(1<<(len))+1][len]))
//#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll ;
#define int ll
#define mod 1000000007
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j) for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//int lcm(int a , int b){return a*b/gcd(a,b);}
//ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define cin(x) scanf("%lld" , &x);
#define endl '
'
const double esp = 1e-6;
const int N = 1e6+9;
const int maxn = 1e3+9;
int dp[maxn][30];
char a[maxn];
int m ;
int len ;
int min(int x , int y){
if(a[x] > a[y]) return y ;
else return x ;
}
void init(){
rep(i , 1 , len){
dp[i][0] = i ;
}
for(int j = 1 ; j <= 10 ; j++){
for(int i = 1 ; i+(1<<j)-1 <= len ; i++){
dp[i][j] = min(dp[i][j-1] , dp[i+(1<<(j-1))][j-1]);
}
}
}
int query(int l , int r){
int len = log2(r-l+1);
return min(dp[l][len] , dp[r-(1<<(len))+1][len]);
}
void solve(){
len = strlen(a+1);
init();
m = len - m ;
int l = 1 , r = len-m+1;
vector<char>v;
while(m--){
l = query(l , r) ;
v.pb(a[l]);
l++;
r++;
}
while(size(v) && *v.begin() == '0') v.erase(v.begin());
if(size(v) == 0) cout << 0 << endl;
else{
for(auto &i : v){
cout << i ;
}
cout << endl;
}
}
signed main()
{
//int _ ;cin>>_;while(_--)
while(~scanf("%s%lld" , a+1 , &m))
solve();
}