使剩下来的数字最大

时间:2021-08-03 05:27:12

这是个裸贪心题。

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

那么不难想到用行列队伍。线性庞大度。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。

不知道怎么搞的。