Zero Quantity Maximization - 题解

比赛与标签

比赛: Codeforces Round 544 (Div. 3) 标签: hashing, math, number theory 难度: *1500

主人，题目是这样的喵~

我们有两个长度都是 n 的整数数组 a 和 b。我们的任务是，找到一个实数 d，然后用它来生成一个新的数组 c，其中每个元素 c[i] 都等于 d * a[i] + b[i]。

我们的目标是，通过聪明地选择 d，让新数组 c 中 0 的数量尽可能地多！最后，我们要告诉裁判，最多能有多少个 0 呐。

简单来说，就是找一个魔法数字 d，让方程 d * a[i] + b[i] = 0 对尽可能多的 i 成立！

喵喵的思考时间！

要把 d * a[i] + b[i] 变成 0，我们来稍微动动小爪子，把这个方程变形一下看看会发生什么吧！

d * a[i] = -b[i]

接下来就要分情况讨论了，就像猫咪看到移动的物体要判断是不是猎物一样，要仔细观察呐！

情况一：当 a[i] 不等于 0 时

这时候，我们可以很轻松地解出 d： d = -b[i] / a[i]

这说明，对于每一个 i（只要 a[i] 不是0），都有一个特定的 d 值能让 c[i] 变成 0。既然我们要找一个 d 让尽可能多的 c[i] 变成 0，那问题就转化成：在所有这些算出来的 d 值中，哪个 d 值出现的次数最多呢？

比如，如果 d = -b[1]/a[1] 和 d = -b[5]/a[5] 算出来是同一个数，那我们只要选择这个 d，就能同时让 c[1] 和 c[5] 都变成 0 啦！

情况二：当 a[i] 等于 0 时

如果 a[i] 是 0，方程就变成了 d * 0 + b[i] = 0，也就是 b[i] = 0。

• 如果 b[i] 也恰好是 0：方程就成了 0 = 0。哇！这个等式对任何 d 值都成立！这意味着，只要 a[i] 和 b[i] 都是 0，c[i] 就永远是 0，不管我们最后选了哪个 d。这些是“白送”的 0，我们必须把它们单独记下来，喵~
• 如果 b[i] 不是 0：方程就成了 b[i] = 0（一个非零的数等于零），这是不可能的！所以这种情况下，c[i] 永远也变不成 0，我们可以直接忽略掉它们。

关键的陷阱：小数点的精度问题！

我们算出来的 d = -b[i] / a[i] 是个实数，可能会是循环小数或者很长的小数。直接用 double 或者 float 类型作为 map 的键来统计次数是非常危险的！因为计算机存小数有精度误差，1.0/3.0 和 2.0/6.0 在计算机里可能不是完全一样的值，这样就会统计出错。

我们聪明的解决方案：用分数！

为了避开小数点的陷阱，我们可以用最纯粹的形式来表示这个比率——分数！ d 对应着分数 -b[i] / a[i]。 只要两个分数化简后是同一个，就代表它们需要的 d 是同一个值。 例如，当 a = [2, 4], b = [-1, -2] 时：

• d_1 = -(-1)/2 = 1/2
• d_2 = -(-2)/4 = 2/41/2 和 2/4 化简后都是 1/2，所以它们是等价的！

为了让分数的表示独一无二（我们称之为“规范化”），我们可以这样做：

1. 把分数 -b[i] / a[i] 化为最简分数。我们可以通过计算分子和分母的最大公约数 (GCD)，然后同时除以它来实现。
2. 规定一个标准形式，比如分母必须是正数。如果化简后分母是负的，就把分子分母同时乘以 -1。例如，1/-2 就变成 -1/2。

这样，每一个比率都有了一个独一无二的 pair<long long, long long> (分子, 分母) 来表示。我们就可以开心地用 map 来统计每个规范化分数出现的次数啦！

最终作战计划！

1. 设置一个计数器 special_zeros，用来统计 a[i] = 0 且 b[i] = 0 的情况。
2. 创建一个 map<pair<long long, long long>, int> 叫做 ratio_counts，来统计每个化简后的分数出现的次数。
3. 遍历数组，对于每个 i：
   • 如果 a[i] == 0，检查 b[i] 是否也为 0，如果是就给 special_zeros 加一。
   • 如果 a[i] != 0，计算出分数 -b[i] / a[i]，将它化简并规范化，然后在 map 中给对应的分数计数加一。
4. 遍历 map，找到出现次数最多的那个分数，记下这个次数 max_freq。
5. 最终答案就是 special_zeros + max_freq！

把想法变成魔法代码喵~

#include <iostream>
#include <vector>
#include <numeric> // 为了使用 std::gcd
#include <map>
#include <utility> // 为了使用 std::pair

// 解决 "Zero Quantity Maximization" 问题的说
// 目标是找到一个实数 'd'，使得数组 'c' (c[i] = d * a[i] + b[i]) 中 0 的数量最大化
void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    std::vector<long long> b(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> b[i];
    }

    // 这个计数器用来存放那些 a[i] 和 b[i] 都是 0 的情况喵~
    // 对于这些数对，无论 d 是多少，c[i] 永远是 0，是白给的零蛋呐！
    int special_zeros = 0;
    
    // 这个 map 用来统计每个 d = -b[i]/a[i] 所需比率的出现次数
    // 用浮点数做 map 的键会有精度问题，非常危险！
    // 所以我们把比率表示成一个最简分数 (分子, 分母) 的标准形式
    std::map<std::pair<long long, long long>, int> ratio_counts;

    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) {
            if (b[i] == 0) {
                // 如果 a[i] = 0 且 b[i] = 0, 那么 d*a[i] + b[i] = 0 对任何 d 都成立
                // 这些零蛋可以和任何一组由 d 决定的零蛋共存
                special_zeros++;
            }
            // 如果 a[i] = 0 但 b[i] != 0, 那么 d*a[i] + b[i] = b[i] != 0
            // 这种情况永远无法变成 0，所以我们直接无视它，喵~
        } else {
            // 要让 c[i] = 0, 我们需要 d * a[i] + b[i] = 0
            // 也就是说 d = -b[i] / a[i]
            long long num = -b[i];
            long long den = a[i];

            // C++17 及以后的 std::gcd 可以正确处理负数输入
            // 它会计算参数绝对值的最大公约数
            long long common_divisor = std::gcd(num, den);

            num /= common_divisor;
            den /= common_divisor;

            // 为了得到一个标准的分数表示，我们确保分母永远是正数
            // 如果分母是负的，就把分子分母都变号，比率的值不变！
            if (den < 0) {
                den = -den;
                num = -num;
            }

            // 找到了这个比率的“身份证”，给它的计数加一！
            ratio_counts[{num, den}]++;
        }
    }

    // 现在，我们来找哪个比率出现的次数最多
    int max_freq = 0;
    for (auto const& [key, val] : ratio_counts) {
        if (val > max_freq) {
            max_freq = val;
        }
    }

    // 最终的答案 = “白送”的零蛋数 + 通过选择最优 d 得到的最大零蛋数
    std::cout << special_zeros + max_freq << std::endl;
}

int main() {
    // 在竞赛编程中，用这个可以加速输入输出，跑得更快哦！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    solve();

    return 0;
}

分析一下有多快喵~

• 时间复杂度: O(N log N) 的说 我们遍历了一次数组，这是 O(N)。在循环里，我们做了 std::gcd 和 map 的插入操作。std::gcd(x, y) 的复杂度大约是 O(log(max(|x|,|y|)))。map 的插入操作是 O(log K)，其中 K 是 map 中不同键的数量（最多为 N）。所以总的时间复杂度是 O(N * (log(Value) + log N))，可以简化为 O(N log N) 呐。

• 空间复杂度: O(N) 的说 在最坏的情况下，所有的比率 -b[i]/a[i] 都是独一无二的，这时我们的 map 需要存储 N 个键值对。每个键是一个 pair。所以空间复杂度是 O(N) 的说。

这次冒险的收获喵~

这道题真有趣，对吧？它教会了我们几件重要的事情：

1. 问题转换: 最核心的思路是把“寻找最优实数 d”的问题，转换成了“寻找出现次数最多的分数”的求众数问题。很多难题都可以通过巧妙的转换变得简单哦！
2. 避开浮点数陷阱: 在需要精确比较实数的时候，优先考虑用分数或者其他整数表示法来代替浮点数，这是一个非常重要且经典的技巧！
3. 数据结构的选择: std::map 是我们统计出现次数的好朋友！它能方便地将一个复杂的东西（比如 pair）作为键，并记录它的频率。
4. 注意边界条件: a[i] = 0 的情况是本题的关键，也是最容易被忽略的陷阱。处理好它，就离成功不远啦！

希望本猫娘的讲解对主人有帮助！下次遇到难题也别怕，我们一起思考，一定能找到办法的！喵~