UVa 11491 Erasing and Winning 题解
2021-02-15 22:25
阅读：367
难度：α
用时：30 min
题目：??
这是个裸贪心题。
题目要求在某数字字符串中删去给定个数的字符，使剩下来的数字最大。
那么不难想到用队列。线性复杂度。0 ms。
每读入一个数，就把之前比较小的拿掉。
注意不能拿太多，否则长度不够。
队满了也不能继续放。（除非有更大的元素可以把队尾的怼下去）
1 for (int i = 0; i ) { 2 char c = getchar(); 3 while (it > 0 && ans[it] d - e) it--; 4 if (it c; 5 } 6 ans[++it] = ‘\0‘; puts(ans+1)
这个速度非常快的，相比我自己的一个想法来说。
经过分析我发现，从原字符串里取出几个数字，每个数字的位置是有限的。首先不能太靠后，其次要在前一个选走的数字之后。
那么算法就是这样的。
1 last = -1; 2 int remain = d - e; 3 for (int i = 1; i ) 4 ans[i] = max_elem(last+1, d - remain + i); // 求最大元素（用 max_element 函数不知道怎么有问题），并记录位置 last。具体实现略
跑了个 700 ms。
果断抄了一个 0 ms 的代码，却跑了个 10 ms。
不知道怎么搞的。
2018-02-06
上一篇：C#中的Math类
下一篇：Window下安装redis
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：UVa 11491 Erasing and Winning 题解
文章链接：http://soscw.com/index.php/essay/55838.html
文章标题：UVa 11491 Erasing and Winning 题解
文章链接：http://soscw.com/index.php/essay/55838.html
评论
亲，登录后才可以留言！