CF131C题解

传送门：https://codeforces.com/problemset/problem/134/C

关注到题目的两个限制：1. 一个人只能与另外同一人交换一张卡牌。2. 一个人只能交换自己原来颜色的卡牌。

对于2条限制条件，显然有贪心思路：尽量让更多的人手持原有的卡牌。对于当前待交换的卡牌，一种构造思路，我们每次贪心选取手中拥有原有牌最多的人进行交换是最优的。

因为如果一个人手中原有的牌被取完就无法与其他人进行交换，显然比从拥有更多原有牌中取更劣。

此过程可以用大根堆维护，当一个人需要交换的卡牌比堆内剩余人数更多则不合法（为满足限制1）。

总时间复杂度 \(O((n+s)log_{2}n)\) 。

#include <bits/stdc++.h>

using namespace std;

inline int read() {
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9') if (c == '-') flag = true;
    int res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';
    return flag ? -res : res;
}

const int _ = 2e5 + 1;

struct Node {
    int val, id;

    bool operator<(const Node &o) const { return val < o.val; }
} a[_];

vector<pair<int, int>> ans;

int main() {
    int n = read(), s = read();
    priority_queue<Node> q;
    for (int i = 1; i <= n; ++i) {
        a[i].val = read(), a[i].id = i;
        if (a[i].val) q.push(a[i]);
    }
    while (!q.empty()) {
        Node o = q.top();
        q.pop();
        if (o.val > q.size()) {
            puts("No");
            return 0;
        }
        vector<Node> tmp;
        while (o.val) {
            Node y = q.top();
            q.pop();
            ans.push_back(make_pair(y.id, o.id));
            --o.val;
            --y.val;
            if (y.val) tmp.push_back(y);
        }
        for (Node k: tmp) q.push(k);
    }
    puts("Yes");
    printf("%zu\n", ans.size());
    for (auto p: ans) printf("%d %d\n", p.first, p.second);
    return 0;
}