题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=3183
题意:
就是给你一个长度为n的数,要求从中去掉m位,剩余位顺序不变,求能得到的最小的数,其中允许得到有前导零的数
解题思路:
比如一个7位数abcdefg删除其中的3位使得最后剩余的数最小,那么最极端的情况就是后面四位全部保留,新数的第一位出现在原数的第四个位置,其他情况下新数的第一位出现在原数的1~3位上
可以知道新数的第一位一定出现在原数的1-n位上(n为要删除的数字个数),因为是按顺序从左到右依次删除的,所以新数的第二位在(记新数的第一位在原数上的第s位)原数上的s+1~m+1位上,以此类推
所以问题的关键在于如何寻找i~j位上的最小数,这就要用到st表了(详情百度叭),st表就是用来求区间的最小/大值问题(RMQ问题)(有点dp的赶脚),它和线段树的预处理时间都是O(nlogn),但是它的查询时间是O(1),而线段树的查询时间是O(nlogn),所以st表的查询操作要比线段树优
但是st表的模版是直接找区间的最小/大值,而我们需要的是最小/大值对应的下标,所以需要对模版稍微修改一下。
st表模版:
void rmq()
{
for(ll i=0;i<len;i++) d[i][0]=a[i];
for(ll j=1;(1<<j)<=len;j++)//长度
{
for(ll i=0;i+(1<<j)-1<len;i++)
{
d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}
}
}
ll query(ll l,ll r)
{
ll k=(ll)(log(r-l+1)/log(2.0));
return min(d[l][k],d[r-(1<<k)+1][k]);
}
ac代码:
#include <iostream>
#include <algorithm>
#include <string>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <sstream>
#define maxn 1005
typedef long long ll;
using namespace std;
string a;
ll d[maxn][20],n,len;
ll Min(ll i,ll j)
{
return a[i]<=a[j]?i:j;
}
void rmq()
{
for(ll i=0;i<len;i++) d[i][0]=I;//注意这里是下标
for(ll j=1;(1<<j)<=len;j++)//长度
{
for(ll i=0;i+(1<<j)-1<len;i++)
{
d[i][j]=Min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}
}
}
ll query(ll l,ll r)
{
ll k=(ll)(log(r-l+1)/log(2.0));
return Min(d[l][k],d[r-(1<<k)+1][k]);
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
while(cin>>a)
{
bool flag=false;
len=a.length();
ll num=0,n;
char ans[maxn];
rmq();
cin>>n;
if(len<=n)
printf("0\n");
else
{
ll s=0,e=n,t=len-n;
while(t--)//剩余t个数字
{
s=query(s,e);
ans[num++]=a[s];
s++;e++;
}
for(ll i=0;i<num;i++)
{
if(!flag && ans[i]=='0') continue;
flag=true;
printf("%c",ans[i]);
}
if(!flag) printf("0");
printf("\n");
}
}
return 0;
}
/*
178543 4
1000001 1
100001 2
12345 2
54321 2
*/