题目概览
描述
There are n players sitting at a round table. All of them have s cards of n colors in total. Besides, initially the first person had cards of only the first color, the second one had cards of only the second color and so on. They can swap the cards by the following rules:
- as the players swap, a player can give a card of his color only;
- a player can’t accept a card of a color he already has (particularly, he can’t take cards of his color, no matter whether he has given out all of them or not);
- during one swap a pair of people swaps cards (each person gives one card and takes one card).
The aim of all n people is as follows: each of them should give out all the cards he had initially (that is, all cards of his color). Your task is to denote whether such sequence of swaps is possible. If the answer is positive, you should list all the swaps.
输入
The first line contains integers n(1\leq n\leq 200000) and s(1\leq s\leq 200000). The second line contains n numbers, the i-th number stands for how many cards the i-th player has by the moment the game starts. It is possible that a player has no cards initially.
输出
On the first line print No if such sequence of swaps is impossible. Otherwise, print Yes. If the answer is positive, next print number k — the number of the swaps. Then on k lines describe the swaps by pairs of indices of the swapping players. Print the swaps and the numbers of the swaps in any order.
大意
有 n 名玩家围成一圈，他们总共有 s 张 n 种不同颜色的卡牌，第 i 名玩家初始拥有 a_i张 i 色卡牌。
玩家可以根据下述规则交换卡牌：
-
当两名玩家交换卡牌时，玩家只能给出自己颜色的卡牌（即玩家 i 只能给出 i 色卡）。
-
玩家不能接受自己已经拥有的颜色的卡牌。
-
每次只交换一张卡牌。
现在每名玩家都想把自己颜色的卡牌交换到其他玩家手中，试判断能否做到这一点。如果可以，输出 Yes 并输出解决方案，否则输出 No。
思路
根据上述规则可知，每两名玩家之间最多只能交换一次卡牌，因此对于任意玩家，其交换次数不会超过 n-1 ，否则这名玩家不可能将他的所有手牌全部交换出去。
又因为每次都有两张卡牌被交换，且卡牌被交换后不可能再次被交换出去，因此当 s 为奇数时也无法满足条件。
考虑最优的交换方案。为了尽可能地让每名玩家都交换出手中的卡牌，应当按照卡牌数从多到少的顺序对玩家进行排序，卡牌数最多的玩家先开始交换，以此类推。对于一名玩家 i ，也应按照其他玩家的卡牌数降序来发起交换。
设玩家 i 为卡牌数最多的玩家，其可以交换的卡牌数为 a_i，即玩家 i 会和除他以外卡牌数最多的 a_i 名玩家交换卡牌。交换过后，被交换卡牌的玩家的可交换卡牌数应 -1 ，然后剩下的玩家中可交换卡牌数最多的玩家再次发起交换，以此类推，直到全部交换完毕，或有玩家不能再交换为止。
值得注意的是如果一名玩家初始没有手牌，他是无法参与交换过程的，因此需要特判一下。
上述过程可以使用优先队列进行维护，时间复杂度为 O(nlogn) 。
实现
#include <bits/stdc++.h>
#define CNO cout << "No\n"
#define CYES cout << "Yes\n"
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int n, s;
ll ans = 0;
string str;
struct Node {
int val, id;
bool operator<(Node x) const { return val < x.val; }
} arr[200010];
vector<pii> v;
priority_queue<Node> q;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--) {
cin >> n >> s;
for (int i = 1; i <= n; ++i) {
cin >> arr[i].val;
arr[i].id = i;
if (arr[i].val) q.push(arr[i]);
}
if (s % 2) {
CNO;
continue;
}
while (!q.empty()) {
Node u1 = q.top();
if (u1.val >= q.size()) break;
q.pop();
vector<Node> tmp;
while (u1.val) {
Node u2 = q.top();
q.pop();
v.push_back({u1.id, u2.id});
tmp.push_back({u2.val - 1, u2.id});
u1.val--;
}
for (Node i : tmp) q.push(i);
}
if (v.size() != s / 2) {
CNO;
continue;
} else
CYES;
cout << v.size() << endl;
for (auto i : v) cout << i.first << ' ' << i.second << endl;
}
return 0;
}
评论