题解：CF1991C Absolute Zero

ELECTRODE_kaf · 2025-02-11 19:35:21 · 题解

既然替换后的数是与所选的数的差，那最佳选择肯定是最大值和最小值的平均值。时间复杂度 O(Qn\log n)。

const ll N = 2e5 + 10, MAX = 40, inf = 3e9;
ll Q, n, a[N];
vector<ll> ans;

int main() {
    sync_off;
    cin >> Q;

    count(Q) {
        ans.clear();
        cin >> n;
        ll min1 = inf, max1 = -inf, cnt = 0;

        rep(i, 1, n) {
            cin >> a[i];
            update(min1, a[i], min);
            update(max1, a[i], max);
        }

        while (1) {
            if (max1 == 0) {
                cout << ans.size() << '\n';

                if (ans.empty() == 0) {
                    for (ll i : ans)
                        cout << i << ' ';
                }

                endl;
                break;
            } else if (cnt == MAX) {
                cout << "-1\n";
                break;
            } else {
                ll x = (min1 + max1) / 2;
                ans.pb(x);
                min1 = inf;
                max1 = -inf;
                cnt++;

                rep(i, 1, n) {
                    a[i] = abs(a[i] - x);
                    update(min1, a[i], min);
                    update(max1, a[i], max);
                }
            }
        }
    }
}