UVa 11491 Erasing and Winning 题解

难度：α

用时：30 min

题目：

这是个裸贪心题。

题目要求在某数字字符串中删去给定个数的字符，使剩下来的数字最大。

那么不难想到用队列。线性复杂度。0 ms。

每读入一个数，就把之前比较小的拿掉。

注意不能拿太多，否则长度不够。

队满了也不能继续放。（除非有更大的元素可以把队尾的怼下去）

1 for (int i = 0; i < d; i++) {
2     char c = getchar();
3     while (it > 0 && ans[it] < c && it + d - i > d - e) it--;
4     if (it < d - e) ans[++it] = c;
5 }
6 ans[++it] = ‘\0‘; puts(ans+1)

这个速度非常快的，相比我自己的一个想法来说。

经过分析我发现，从原字符串里取出几个数字，每个数字的位置是有限的。首先不能太靠后，其次要在前一个选走的数字之后。

那么算法就是这样的。

1 last = -1;
2 int remain = d - e;
3 for (int i = 1; i <= remain; i++)
4     ans[i] = max_elem(last+1, d - remain + i); // 求最大元素（用 max_element 函数不知道怎么有问题），并记录位置 last。具体实现略

跑了个 700 ms。

果断抄了一个 0 ms 的代码，却跑了个 10 ms。

不知道怎么搞的。

2018-02-06