给你一个数,不超过2000位,让你删去其中m位数字,删除完后,剩下的数字顺序不变,求怎么删除数字最小。

这道题是一道ST表入门题目。

首先先来介绍一波ST:

ST表算法详解(求最小值): 
用mn[i][j]表示从j到j+2^i-1的最小值(长度显然为2^i)。 
任意一段的最小值显然等于min(前半段最小值,后半段最小值)。 
那么mn[i][j]如何用其他状态来继承呢? 
j到j+2^i-1的长度为2^i,那么一半的长度就等于2^(i-1)。 
那么前半段的状态表示为mn[i-1][j]。 
后半段的长度也为2^(i-1),起始位置为j+2^(i-1)。 
那么后半段的状态表示为mn[i-1][j+2^(i-1)]。 
所以: 
mn[i][j]=min(mn[i-1][j],mn[i-1][j+2^(i-1)]。
线段树预处理O(nlogn),查询O(logn),支持在线修改 
ST表预处理O(nlogn),查询O(1),但不支持在线修改 

题解:

这个数如果有n位,要删除m个,那么第一个只能在第1位到第n-m-1位,第二个则是在第2到第n-m,以此类推, 求出这些区间内的最小值即可。

题目链接

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

int f[2005][2005];
char ss[2005], num[2005];
int m, n;

int min(int i,int j) {//比较字符大小 
	return ss[i]<=ss[j] ? i:j;
}

void ST() {
	int i, j;
	for(int i = 0; i < n; i++) {
		f[i][0] = i; //初始化 每个长度为1的区间初始值为其本身
	}
	for(j = 1; j <= (int)(log((double)n)/log(2.0)); j++) {
		for(i=0; i+(1<<j)-1<n; i++) {
			f[i][j] = min(f[i][j-1], f[i+(1<<(j-1))][j-1]);
		}

	}
}

int que(int l, int r) {//查询区间 
	int x = (int)(log((double)(r-l+1))/log(2.0));
	return min(f[l][x], f[r-(1<<x)+1][x]);
}
int main() {
	while(~scanf("%s%d", ss, &m)) {
		n = strlen(ss);
		m = n - m;
		ST();
		int i = 0;
		int j = 0;
		while(m--) {//查找区间最小值
			i = que(i, n-m-1);
			num[j++] = ss[i++];
		}
		for(i = 0; i < j; i++) { //判断第一个0的位置
			if(num[i] != '0') {
				break;
			}
		}
		if(i == j) { //如果每一位都为0,则直接输出打印0
			printf("0\n");
			continue;
		}
		while(i < j) {
			printf("%c",num[i]);//从第一个不为0的数开始打印
			i++;
		}
		printf("\n");
	}
	return 0;
}