CF1991C Absolute Zero

原题链接：C. Absolute Zero

Tag：观察

题目描述

给定一个长度为 \(n\) 的数组 \(a\)。

在一次操作中，我们可以指定一个数字 \(x(0 \leq x \leq 10^9)\)。 把每一个 \(a_i\) 替换为 \(|a_i - x|\)。

问是否可以在 \(40\) 次操作中让 \(a\) 中的所有元素变成 \(0\)， 如果可以的话输出这个操作序列。

分析

首先可以分析一下在什么时候是无解的， 手玩一下最后一个样例会发现， 我们在不断尝试缩小数值的时候会发现， 这个样例最后会变成若干个 \(1\) 和 若干个 \(0\)， 这个时候我们取什么数字多少次都无法全变成 \(0\)， 所以无解的情况就是当数组中同时存在奇数和偶数的情况。

在知道了如何判断是否无解之后， 我们可以选择每次将数组中最大值的一半设置为 \(x\)， 这样一来每次操作之后都会缩小最大值的一半， 这是一个类似于二分的过程， 可以得出最多执行 \(log\) 次， 因此 \(40\) 次操作是完全够的。

代码实现

void NeverSayNever() {
    int n;
    cin >> n;
    int cnt = 0;
    vector<int> vec(n);
    vector<int> ans;
    for (auto &x: vec) cin >> x;
    for (;;) {
        int mx;
        bool num = false;
        for (auto &x: vec) if (!x) num = true;
        mx = *std::max_element(vec.begin(), vec.end());
        if (mx == 1) {
            cnt++;
            ans.push_back(1);
            if (num) {
                cnt = -1;
            }
            break;
        } else if (mx > 0) {
            cnt++;
            ans.push_back(mx / 2);
            for (int i = 0; i < n; i++) {
                vec[i] = abs(vec[i] - mx / 2);
            }
        } else {
            break;
        }
    }
    if (cnt == -1) {
        cout << -1 << endl;
    } else {
        cout << cnt << endl;
        if (cnt >= 0) {
            for (auto &x: ans) cout << x << ' ';
            cout << endl;
        }
    }
}

额外思考

好像没什么值得额外思考的。

日志

本页面创建于 2024/7/30 01:40