CF1989C Two Movies 题解

题意简述

有两部电影，$n$ 个观众。第 $i$ 个观众对第一部电影的评价为 $a_i$，对第二部的评价为 $b_i$，$a_i,b_i\in\{-1,0,1\}$。

我们要为每个观众推荐去看其中一部电影（每人只看一部）。若观众去看电影 1，则电影 1 总分加上 $a_i$；若去看电影 2，则电影 2 总分加上 $b_i$。公司最终得分为 两部电影总分的较小值。求这个最小值的最大值。

核心思路：贪心 + 平衡

设最终电影 1 的总分为 $X$，电影 2 的总分为 $Y$，目标是最大化 $\min(X,Y)$。

对于每个观众 $i$，有两种选择：

• 选电影 1：贡献 $(a_i,0)$
• 选电影 2：贡献 $(0,b_i)$

第一步：确定明确优势的选择

若 $a_i > b_i$，则选电影 1 一定不劣：不仅让 $X$ 增加了 $a_i$，还避免了 $Y$ 增加较小的 $b_i$。同理，若 $b_i > a_i$，则选电影 2 一定不劣。

这些选择可以直接固定下来，不会漏掉最优解。

第二步：处理平局 $a_i = b_i$

对于 $a_i = b_i$ 的情况，两种选择对两电影的影响是等效的：都会使某部电影增加 $c_i = a_i$，另一部不变。我们需要借助这些“可调”的分数来平衡 $X$ 和 $Y$。

• 若 $c_i = -1$：相当于要扣掉某部电影的 1 分。为了最大化 $\min(X,Y)$，应该扣掉当前较大者，使两者更接近。
• 若 $c_i = +1$：相当于赠送 1 分。应加给当前较小者，提升短板。
• 若 $c_i = 0$：分配不影响结果，可以忽略。

重复以上操作直到所有平局观众处理完毕，此时 $\min(X,Y)$ 即为答案。

正确性简要说明

先固定明确优势的选择不会丢失最优解，因为交换论证可证：若最优解中出现了违背的情况，可以交换得到不差的结果。

对于平局部分，每次局部最优的平衡操作可以通过调整法证明整体最小值的最大化。直觉上，我们的操作总是尽量让 $X$ 和 $Y$ 接近，从而最大化较小值。

算法步骤

1. 读取 $n$ 和数组 $a,b$。
2. 初始化 $X = 0$，$Y = 0$。
3. 遍历 $i = 1 \sim n$：
   • 若 $a_i > b_i$，$X \mathrel{+}= a_i$；
   • 若 $b_i > a_i$，$Y \mathrel{+}= b_i$；
   • 若 $a_i = b_i$，将 $a_i$ 存入暂存列表。
4. 遍历暂存列表中的每个值 $c$：
   • 若 $c = -1$：若 $X \ge Y$ 则 $X \mathrel{-}= 1$，否则 $Y \mathrel{-}= 1$；
   • 若 $c = +1$：若 $X \ge Y$ 则 $Y \mathrel{+}= 1$，否则 $X \mathrel{+}= 1$；
   • 若 $c = 0$：忽略。
5. 输出 $\min(X,Y)$。

复杂度

• 每组数据遍历数组 $O(n)$，总 $\sum n \le 2\times 10^5$，$t \le 10^4$，总复杂度 $O(\sum n)$，可以在时限内轻松通过。

参考代码

#include <iostream>
using namespace std;

const int N = 200005;
int t, n;
int a[N], b[N];
int ansa, ansb;
int c[N], s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while (t--) {
        ansa = ansb = s = 0;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 1; i <= n; ++i) cin >> b[i];
        
        // 第一步：处理 a_i > b_i 或 b_i > a_i 的情况
        for (int i = 1; i <= n; ++i) {
            if (a[i] > b[i]) ansa += a[i];
            else if (b[i] > a[i]) ansb += b[i];
            else c[++s] = a[i]; // a[i] == b[i]
        }
        
        // 第二步：处理平局，用 c[i] 平衡两分数
        for (int i = 1; i <= s; ++i) {
            if (c[i] < 0) {          // -1
                if (ansa >= ansb) ansa -= 1;
                else ansb -= 1;
            } else if (c[i] > 0) {   // +1
                if (ansa >= ansb) ansb += 1;
                else ansa += 1;
            }
            // c[i] == 0 不操作
        }
        
        cout << min(ansa, ansb) << '\n';
    }
    return 0;
}