hdu 3183 A Magic Lamp （rmq）

ysoren

　　题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3183



#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
/**
rmq 问题：题意很简单，求一行数字中除去其中m个数字，使其组成最小的一个数字
使用rmq解题，设源数字长为n，那么除去m个数字后剩下的还剩n-m个数字，组成最小的数字。
（1）因为剩下n-m个数字，那么在1到m+1位置中最小的那个数字必是结果中的第一个数字i，
（2）然后从这个数字i位置的下个位置i+1开始到m+2位置的数字中最小的那个数字必定是
结果中第二个数字，以此类推下去向后找。
（3）为了保证数字最小所以要保证高位最小还要保证数字长度够用~~
**/
char num[1010];
char res[1020];
int dp_min[1010][20];
int t;
//返回较小值
int mins(int a,int b)
{
return num[a]<=num?a:b;
}
void rmq_init(int len)
{
for(int i = 0; i < len; i++)
dp_min[0] = i;
for(int j = 1; (1<<j) < len; j++)
for(int i = 0; i+(1<<j)-1 < len;i++)
dp_min[j] = mins(dp_min[j-1],dp_min[i+(1<<(j-1))][j-1]);
}
int query(int l,int r)
{
int k = (int)(log((double)(r-l+1))/log(2.0));
return mins(dp_min[l][k],dp_min[r-(1<<k)+1][k]);
}
int main()
{
int len;
while(scanf("%s%d",num,&t)!=EOF)
{
len = strlen(num);
rmq_init(len);
int m = len-t;
int p = 0,j=0;
while(m--)
{
p=query(p,len-m-1);
res[j++] = num[p++];
}
for(p = 0; p < j; p++)
if(res[p]!='0')break;
if(p==j)printf("0");
else
{
while(p<j)
printf("%c",res[p++]);
}
puts("");
}
return 0;
}