CF1474C Array Destruction

给定2n个数。
求x，满足：

1. x可以由这2n个数中的两个数组成
2. 将这两个数中的较大值作为x
3. 从2n个数中剔除去这两个数
4. 若2n个数能全部被剔除，则输出YES并输出这2n个数剔除的顺序，否则输出NO

x一定由这剩下的数中最大的数和另一个数组成。假如不包含剩下的数中最大的数，则x会小于剩下的数中最大的数，则2n个数不可能被全部剔除。
知道这点，用multiset模拟就方便很多了。
熟悉一下map和pair嵌套的用法。以及multiset的用法。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;

int read(){
	char ch=getchar();
	int x=0,f=1;
	while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}
	while(ch>=‘0‘&&ch<=‘9‘) x=x*10+(ch^48),ch=getchar();
	return x*f;
}

vector<pair<int, int> > check(int n, vector<int> v, int x)
{
    multiset<int> s;
    vector<pair<int, int> > res;
    for (auto e : v) s.insert(e);
    for (int i = 0; i < n; i++)
    {
        auto it1 = s.end();
        it1--;
        int y = x - *it1;
        s.erase(it1);
        auto it2 = s.find(y);
        if(it2 == s.end()) return {};
        res.push_back(make_pair(x-y, y));
        s.erase(it2);
        x = max(x - y, y);
    }
    return res;
}

void solve(){
    vector<int> v;
    int n = read();
    for (int i = 0; i < 2 * n; i++) v.push_back(read());
    sort(v.begin(), v.end());
    for (int i = 0; i < 2 * n; i++)
    {
        vector<pair<int, int> > res;
        res = check(n, v, v[i] + v[2 * n - 1]);
        if (res.size())
        {
            puts("YES");
            cout << v[i] + v[2 * n - 1] << ‘\n‘;
            for (int i = 0; i < n; i++)
            {
                cout << res[i].first << " " << res[i].second << ‘\n‘;
            }
            return;
        }
    }
    puts("NO");
}

int main(){
    int t;cin>>t;
    while(t--){
        solve();
    }
}

CF1474C Array Destruction

原文：https://www.cnblogs.com/clo91eaf/p/14528415.html