CodeForces - 749C Voting

这是一道 CodeForces 上的题目，题目编号为 749C，题目名称为 Voting。

题目描述：

有 $n$ 个人参加选举，选出一位领导人。每个人都会投票，你知道了每个人选择谁，并且可以知道选票中作废票和弃权票的数量。如果有一个人获得了半数以上的有效选票（即除去作废票和弃权票的票数），那么他将成为领导人。如果没有任何一个人获得半数以上的有效选票，则选举无效。

现在你可以修改任意数量的作废票或弃权票，使选举有效，并使你支持的候选人成为领导人。你需要最少的修改次数。

输入格式：

第一行包含三个整数 $n, a, b$，分别表示选民的数量，作废票的数量和弃权票的数量。

接下来 $n$ 行，每行包含一个字符串，表示每个人的投票情况。如果该字符串为 “YES” 或 “NO”，表示该选民对应的是弃权票；如果该字符串为 “POLL”, 表示该选民对应的是作废票；如果该字符串为其他字符串，则表示该选民对应的是有效选票，该字符串为该选民的投票对象。

输出格式：

如果无法通过修改使选举有效，则输出 -1；否则输出最少的修改次数，使得选举有效，并且你支持的候选人成为领导人。

数据范围：

$1 \leq n \leq 2000, 0 \leq a, b \leq n$

输入样例 #1：

7 2 1
YES
NO
POLL
YES
YES
YES
NO

输出样例 #1：

1

样例 #1 解释：

总共有7个选民，其中弃权票有3个，作废票有2个，有效选票有2个。由于选民投票意见分散，无法确定一位领导人，因此选举无效。

我们可以将2张作废票修改为支持你所支持的候选人，这样你所支持的候选人将获得3张有效选票，超过半数，成为领导人。因此修改次数为1。

输入样例 #2：

3 1 0
YES
NO
YES

输出样例 #2：

0

样例 #2 解释：

总共有3个选民，其中弃权票有1个，作废票有0个，有效选票有2个。你所支持的候选人获得了2张有效选票，超过半数，成为领导人。由于选民投票意见不分散，选举有效，无需修改任何票。因此修改次数为0。

算法1：

(模拟) $O(n)$

首先计算出除作废票和弃权票之外的票数，如果有一人的得票率超过50%，则选举有效，直接输出0。

否则，需要计算出至少需要修改多少张作废票或弃权票，才能使选举有效，并且支持你所支持的候选人成为领导人。

具体来说，我们可以考虑枚举需要修改的作废票和弃权票的数量，假设需要修改 $i$ 张作废票和 $j$ 张弃权票，使得选举有效。那么，你所支持的候选人需要得到至少 $\lceil \frac{n}{2} \rceil$ 张有效选票。我们可以通过统计当前你所支持的候选人得到的有效选票数 $cnt$，以及当前已经修改的作废票和弃权票的数量 $a'$ 和 $b'$，来判断是否存在一组解 $(i, j)$，使得选举有效。

具体来说，如果当前得票数 $cnt + i \ge \lceil \frac{n}{2} \rceil$，那么选举有效，输出 $i+j$ 即可。如果 $(\lceil \frac{n}{2} \rceil - cnt) \le a' + i \le n-b'-j$，那么也存在一组解 $(i,j)$，使得选举有效，输出 $i+j$ 即可。

如果枚举完所有情况，都无法使选举有效，那么输出 -1。

时间复杂度：$O(n^2)$

C++ 代码