「AGC 053」B - Taking the middle

本文主要是介绍「AGC 053」B - Taking the middle，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

需要最小化后手的得分，容易发现后手在 \(n - i + 1...n + i\) 中至少选了 \(i\) 个。

这是因为第 \(i\) 此时还剩下 \(2*(n - i) + 1\) 个，然后就算两端 \(n - i\) 个位置全都在，中间还会有一个也显然会选它。

是否满足该条件就可以了？考虑构造方案：

将后手选的记为 \(1\)，先手选的记为 \(-1\)，然后 \(s_i = \sum_{j\in [n -i + 1, n + i]} a_j\)。

满足 \(\forall s_i \ge 0\)， \(s_n\) = 0。

从中间往两端进行操作：

如果最中间的两个不同，则选择将它们消去， \(s_i +1 - 1 = s_i\)，不变。

否则恰好为 \((1,1)\)，于是可以将最靠内的一对 \((-1,-1)\) 给抵消了，因为其间均为 \((-1,1)\) 或 \((1, 1)\)，消去 \((1,1)\) 后 \(s\) 不会变负。

那么问题就是需要在 \(n - i + 1...n + i\) 中至少选 \(i\) 个，最小化总权值。

然后从中间开始，每次将最内的两个加入小根堆，在将堆顶元素取出即可。

代码

这篇关于「AGC 053」B - Taking the middle的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！