题解归档 - cf406B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf406B
• 本地来源：problems/cf406B/idea.md
• 题目链接：https://codeforces.com/contest/406/problem/B
• 原始标题：cf406B - Toy Sum

思路

cf406B - Toy Sum

Let S=1e6. Need sum(x-1) = sum(S-y).

For every taken block x, the complement S+1-x contributes exactly x-1 on the right. If only one number of a complement pair {i,S+1-i} is in X, put the other one in Y.

If both numbers of a complement pair are in X, their total left contribution is (i-1)+(S-i)=S-1. Any empty complement pair {a,S+1-a} not intersecting X also contributes (S-a)+(a-1)=S-1, so use one empty pair for each full pair. There are enough empty pairs because among S/2=5e5 complement pairs and n<=5e5 taken numbers, the count of empty pairs is at least the count of full pairs.

代码

来源：problems/cf406B/solution.cpp

#include <bits/stdc++.h>
using namespace std;

const int S = 1000000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> x(n);
    vector<char> pd(S + 2);
    for (int &v : x) {
        cin >> v;
        pd[v] = 1;
    }

    vector<int> ans;
    vector<int> emp;
    int need = 0;
    for (int i = 1; i <= S / 2; i++) {
        int j = S + 1 - i;
        if (pd[i] && pd[j]) {
            need++;
        } else if (pd[i]) {
            ans.push_back(j);
        } else if (pd[j]) {
            ans.push_back(i);
        } else {
            emp.push_back(i);
        }
    }
    for (int i = 0; i < need; i++) {
        int a = emp[i], b = S + 1 - a;
        ans.push_back(a);
        ans.push_back(b);
    }

    cout << ans.size() << '\n';
    for (int v : ans) cout << v << ' ';
    cout << '\n';
    return 0;
}