【题解】AT_abc027_d [ABC027D] ロボット

YuYuanPQ · 2024-06-16 21:40:32 · 题解

算是贪心的题吧。

我们约定下文中：

d 数组表示：输入的字符串；

cnt 表示：当前贡献。

s 数组表示：d[i] 为 M 时 cnt 的值；

l 表示：s 数组的长度，也就是 d 中 M 的个数。

分类讨论一下：

• 当 d[i] 为 + 时，i 对正方向的贡献为 1，cnt++。

• 当 d[i] 为 - 时，i 对负方向的贡献为 1，cnt--。

• 当 d[i] 为 M 时，把 cnt 放进 s 数组。显然，如果 i 的后面没有 + 或者 -，这个位置无贡献。

把 s 数组从小到大排序。

因为前面一半的 l/2 个 s[i] 贡献最小，所以我们选择减去它们，后面一半的 s[i] 贡献大，所以加上它们。

输出答案即可。

完结撒花~

Code

Link