【HDU 3183】下标RMQ

【HDU 3183】下标RMQ

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

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

#includeconst 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。