题解：CF1474C Array Destruction

sccc_ · 2025-08-11 09:47:26 · 题解

Solution

对于这道题的 x，我们只能选择数组中最大的数字与其他一个数字的和，否则更大的就无法删除。

每次选择较大的数 a_i，另一个数就是 x - a_i，若 x - a_i 不存在，即此方案无解。否则将 x 设为 a_i，记录答案，然后一直循环此过程到结束或无解。

若所有方案都无解，输出 NO。

#include <bits/stdc++.h>

using namespace std;

const int N = 2005;

int n, a[N], cnt;

struct Ans {
    int x, y;
} ans[N];

bool check(int idx, unordered_map<int, int> mp) {
    cnt = 1;
    ans[cnt] = {a[idx], a[n]};
    int x = a[n];
    mp[a[idx]]--, mp[a[n]]--;
    for (int i = n - 1; cnt < n / 2; i--) {
        if (mp[a[i]] == 0)
            continue;
        if ((a[i] == x / 2 && mp[a[i]] < 2) || (mp[x - a[i]] == 0)) {
            return 0;
        }
        mp[a[i]]--, mp[x - a[i]]--;
        ans[++cnt] = {a[i], x - a[i]};
        x = a[i];
    }
    return cnt == n / 2;
}

signed main() {
    cin.tie(0), cout.tie(0)->sync_with_stdio(false);
    int t;
    for (cin >> t; t--;) {
        cin >> n;
        n <<= 1;
        unordered_map<int, int> mp;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            mp[a[i]]++;
        }
        sort (a + 1, a + 1 + n);
        bool f = 0;
        int idx;
        for (int i = 1; i <= n - 1; i++) {
            if (check(i, mp)) {
                f = 1;
                idx = i;
                break;
            }
        }
        if (f) {
            cout << "YES\n";
            cout << a[n] + a[idx] << '\n';
            for (int i = 1; i <= cnt; i++) {
                cout << ans[i].x << ' ' << ans[i].y << '\n';
            }
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}