hduacm 3183 rmq

时间:2022-03-29 14:41:27

http://acm.hdu.edu.cn/showproblem.php?pid=3183

问题等价与取N-M个数,每次取的时候保证后面能取的个数足够,并且取的数最小  查询最小用rmq

 #include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring> using namespace std; const int maxn = + ; int N,M,d[maxn][];
char s[maxn]; struct RMQ{
void init()
{
N = strlen(s);
for (int i = ;i<N;i++)
d[i][] = s[i];
for (int k = ;(<<k)<=N;k++)
{
for (int i = ;i<N;i++)
d[i][k] = min(d[i][k-],d[i+(<<(k-))][k-]); }
}
int query(int L,int R)
{
int k = ;
while (<<(k+)<=R-L+) k++;
return min(d[L][k],d[R-(<<k)+][k]);
}
}; RMQ rmq; int main()
{
while (~scanf("%s%d",s,&M))
{
rmq.init();
M = N - M;
int mv = ;
bool flag = true;
for (int i = M;i;i--)
{
int c = rmq.query(mv,N-i);
while (mv<N&&s[mv]!=c) mv++;
mv++;
if (c==''&&flag)
continue;
flag = false;
printf("%c",c); }
if (flag)
printf("");
printf("\n");
}
return ;
}