CF1579D-Productive Meeting

2022-04-27 题解

题目大意：一共有n个人，每个人都可以和其他人进行若干次一对一的谈话，第i个人可以谈话 $a_i$ 次，问所有人最终总共能有多少次谈话，并输出谈话方案。

考虑下面这个案例

1
2

3
2 2 2

如果一直让第一个人跟第二个人谈话，最终的谈话只有两次。而最多的谈话却能有3次，下面是一种方案

1
2
3

1 2
1 3
2 3

如果一直让第一个人跟第二个人谈话，第三个人的谈话次数最终都生下来，浪费掉了。上述方法充分使用到每一个人的剩余次数，减少了浪费，增加了最终总的谈话数。

如何尽量减少浪费？可以每次取剩余次数最大的两个人，让他们谈话。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, i, j, a, _;
    scanf("%d", &_);
    while (_--)
    {
        scanf("%d", &n);
        priority_queue<pair<int, int>> pq;
        for (i = 1; i <= n; i++)
        {
            scanf("%d", &a);
            if (a > 0)
                pq.push(make_pair(a, i));
        }
        queue<pair<int, int>> res;
        pair<int, int> p;
        while (pq.size() > 1)
        {
            p.first = pq.top().second;
            i = pq.top().first;
            pq.pop();
            p.second = pq.top().second;
            j = pq.top().first;
            pq.pop();
            res.push(p);
            if (--i)
                pq.push(make_pair(i, p.first));
            if (--j)
                pq.push(make_pair(j, p.second));
        }
        printf("%d\n", res.size());
        while (!res.empty())
        {
            printf("%d %d\n", res.front().first, res.front().second);
            res.pop();
        }
    }
    return 0;
}