https://codeforces.com/problemset/problem/1579/D

题目大意

        有 n 个人被邀请参加一个即将召开重要会议。在会议中，任意两个人可以社交，相同的两个人可以社交任意次。

        n 个人中，每个人都有一个社交能力值，其中第 i 个人的社交能力值是一个非负整数 ai，它表示这个人可以与另一个人社交的次数。

       在一个会议中，产生的社交次数越多，这次会议就会被认为越有效。具体地，一个会议的有效程度为这次会议进行时产生的社交次数。

        给你序列 a，求出一次会议的最大有效程度，要求给出任意一种可以产生这个最大有效程度的方案。

 贪心思路：

一旦我们选不出 2 个大于 0 的数，就只能结束操作。

于是一个简单的贪心思路：每次选择最大和次大，使它们都 -1。

反证法：

• 如果不选择最大和次大而是选择其它的数 -1，那么这些被减的数一定比选择最大和次大 -1 更接近 0。

  一旦一个数字被减到 0，那么它在之后的决策中就不可以被选，而选不出 2 个大于 0 的数，就意味着必须结束选择。

  由于我们要最大化选择次数，所以我们希望能选出 2 个大于 0 的数的次数尽可能的多，也就是使得可以被选择的数的数量尽可能多。

  而选择非最大、次大的数会导致可以选择的数的数量更快的减小，故选择最大、次大两个数一定不会更劣。

  综上，每次贪心的选择最大、次大两个数是正确的。

• 然后维护最大和次大用优先队列即可

代码实现：

#include 
#include 
#include using namespace std;
#define pi acos(-1.0)
#define endl '\n'
#define x first
#define y second
typedef long long LL;
typedef pair PII;void solve()
{priority_queue pq;  // 优先队列值为优先vector vv;  // 存答案int n,c;LL ma = 0;  // 谈话次数cin >> n;for (int i = 1; i <= n; i ++ ){cin >> c;pq.push({c,i});  // 存值和下标}PII m1, m2;while(1){m1 = pq.top();pq.pop();m2 = pq.top();pq.pop();if(m2.x == 0 || m1.x == 0) break;  // 当出现0即没有答案，跳出vv.push_back({m1.y,m2.y});  // 存答案ma ++;m1.x -= 1; m2.x -= 1;pq.push(m1);pq.push(m2);}cout << ma << endl;for(LL i = 0; i < vv.size(); i ++) cout << vv[i].x << " " << vv[i].y << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);int T = 1;cin >> T;while(T --){solve();}return 0;
}