【HDU 3183】下标RMQ

1.​​题目链接​​。题目大意：给定一个n位的十进制数，删去m位，让剩下的值最小。

2.这个题目显然贪心，开始想的是从前到后查找逆序删除，因为从高位删除是最优（此处没有证明。。。。），然后删除每一个元素之后，就继续对这个数组进行相同的操作，循环m次即可。涉及到元素的删除，我们可以下一个双向的链表来实现这个操作。但是仔细的想一下，因为删除的过程中，我们需要保持余下的元素相对位置不变，其实就是说挑选n-m个最小的元素。那么我们对每个元素分析，第一个元素所在的区间一定是[1,m](假设这里下表从1开始）。因为如果这个区间不选任何元素，那么一定是选不够的。这个就是鸽巢原理了吧，所以我们做m次RMQ，这里的RMQ是其实是在记录下标。

#include<bits/stdc++.h>
const int N = 1100;
#pragma warning(disable:4996)
int a[N];
int dp[N][20];
using namespace std;
void RMQMinIndex(int n, int b[])
{
for (int i = 0; i < n; i++)
dp[i][0] = i;
for (int j = 1; (1 << j) <= n; j++)
for (int i = 0; i + (1 << j) - 1 < n; i++)
dp[i][j] = b[dp[i][j - 1]] <= b[dp[i + (1 << (j - 1))][j - 1]] ? dp[i][j - 1] : dp[i + (1 << (j - 1))][j - 1];
}
int qMinIndex(int s, int v, int b[])
{
int k = (int)(log(v - s + 1) / log(2));
return b[dp[s][k]] <= b[dp[v - (1 << k) + 1][k]] ? dp[s][k] : dp[v - (1 << k) + 1][k];
}

char str[N];
int ans[N];
int m;
int main()
{
while (~scanf("%s%d", &str, &m))
{
int n = strlen(str);
for (int i = 0; i < n; i++)a[i] = str[i] - '0';
RMQMinIndex(n, a);
int t = 0, temp = 0;
for (int i = m; i < n; i++)
{
t = qMinIndex(t, i, a);
ans[temp++] = a[t++];
}
t = 0;
while (t < temp&&ans[t] == 0)t++;
if (t >= temp)printf("0\n");
else
{
for (int i = t; i < temp; i++)printf("%d",ans[i]);
printf("\n");
}
}
return 0;
}