hdu 3183 A Magic Lamp RMQ ST 坐标最小值
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3183
题目大意：
从给定的串中挑出来m个数使得剩余的数字最小，串的序列不能改变
思路：
- 将问题转化为求在n个数中挑选n-m个数，使之最小。假设最极端的情况，所有最大的数字都在左侧，占据了m个位置，那么我们需要挑选的最小的数字的第一位就是在m+1位上。依次类推，第二位在m+2位上，最后一位也就在原串的最后一位上。反过来，假设最大的数字都在右侧，占了m个位置。那么我们需要挑选的最小数字的最后一位就是在n-m位上，倒数第二位在n-m-1位上，最终最后一位就是在第一位上。至此，可以得到我们挑选最小数的第一位的取值范围就是[1,m+1]。类比可得，第二位取值范围[2,m+2]，...。假设我们此时已经求出了第一位所在的位置x，那么第二位数字的范围就可以进一步缩小为[x+1,m+2]，依次我们可以求出全部的数字。同时要注意，ST表中保存的是该段区间最小值的下标。
- ST在线 预处理O(nlogn) 查询O(1) 运行时间：15ms
- 这道题注意的细节有很多，写了很久才敢提交还是WA了3发。/(ㄒoㄒ)/~~要注意题中说n不会大于串的长度是不成立的，要来特判
代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
const int maxn = 1005;
int minindex[maxn][10],data[maxn],res[maxn];
inline void init(int len) {
for(int i=1; i<=len; ++i) minindex[i][0]=i;
for(int j=1; j<=10; ++j) {
for(int i=1; i<=len; ++i) {
if((i+(1<<j)-1)<=len) {
int t1=minindex[i][j-1],t2=minindex[i+(1<<(j-1))][j-1];
if(data[t1]<=data[t2]) minindex[i][j]=t1;
else minindex[i][j]=t2;
}
}
}
}
inline int ask(int l, int r) {
int k=31-__builtin_clz(r-l+1);
int t1=minindex[l][k],t2=minindex[r-(1<<k)+1][k];
if(data[t1]<=data[t2]) return t1;
else return t2;
}
int main() {
char s[1005];
int n,len,l,r,ip1,ip2;
while(~scanf("%s %d",s,&n)) {
memset(minindex,0,sizeof(minindex));
len=strlen(s);
for(int i=0; i<len; ++i) {
data[i+1]=s[i]-'0';
}
if(n>=len) {
printf("0\n");
continue;
}
init(len);
len=len-n;
l=1,r=n+1;
ip2=1;
for(int i=1; i<=len; ++i) {
ip1=ask(l,r);
res[ip2]=data[ip1];
++ip2;
l=ip1+1;
++r;
}
ip2--;
for(l=1; l<=ip2; ++l) {
if(res[l]) break;
}
if(l>ip2) {
printf("0\n");
continue;
}
for(int i=l; i<=ip2; ++i) printf("%d",res[i]);
printf("\n");
}
return 0;
}