D. Productive Meeting

🤝 D. 高效会议（Productive Meeting）

时间限制： 2 秒 内存限制： 256 MB

---

📘 题目描述

即将召开一场重要会议，会议中 恰好有 n 个人参加。

在会议进行过程中，任意两个人 可以暂时离开大组，进行一次 私下交谈。 同一对人 可以在会议期间交谈多次，没有限制。

---

🧑‍🤝‍🧑 社交度说明

每个人的社交能力是有限的。

• 第 i 个人的社交度为 a_i（非负整数）
• 含义是： 👉 这个人 最多只能参与 a_i 次交谈
• 当某人 恰好参与了 a_i 次交谈后，他就会 离开会议，不再与任何人交谈
• 如果 a_i = 0，那么这个人 会议一开始就离开

---

🎯 会议目标

一次会议被认为是 “最高效的”，如果在会议期间：

发生的交谈总次数尽可能多

你的任务是：

• 给定所有人的社交度数组 a
• 安排哪些人和哪些人进行交谈
• 使得 总交谈次数最大

---

📥 输入格式

• 第一行：一个整数 t 表示测试用例数量

• 接下来 2t 行，描述 t 组测试用例：

每个测试用例的格式

1. 第一行：一个整数 n 表示会议中参与的人数

2. 第二行：n 个整数

   a1, a2, …, an
   

   表示每个人的社交度

---

📤 输出格式

对于每个测试用例，输出如下内容：

1. 第一行：一个整数 k 表示会议中 最多可能发生的交谈次数

2. 接下来 k 行： 每行输出两个整数 i 和 j（i ≠ j） 表示 第 i 个人与第 j 个人进行了一次交谈

⚠️ 注意：

• 若存在多种最优方案，输出任意一种即可
• 同一对人可以出现多次

---

📌 数据范围

• 1 ≤ t ≤ 1000

• 2 ≤ n ≤ 2 × 10^5

• 0 ≤ a_i ≤ 2 × 10^5

• 所有测试用例中：

  • n 的总和 ≤ 2 × 10^5
  • a_i 的总和 ≤ 2 × 10^5

---

🧪 样例输入

8
2
2 3
3
1 2 3
4
1 2 3 4
3
0 0 2
2
6 2
3
0 0 2
5
8 2 0 1 1
5
0 1 0 0 6

---

🧪 样例输出（其中一种可能）

2
1 2
1 2
3
1 3
2 3
2 3
5
1 3
2 4
2 4
3 4
3 4
0
2
1 2
1 2
0
4
1 2
1 5
1 4
1 2
1
5 2

---

📝 样例说明（直观理解）

• 每一次输出 (i, j)，表示：

  • 第 i 个人和第 j 个人各消耗 1 点社交度

• 每个人参与的总次数 不能超过 a_i

• 当某人的社交度用完，就不能再出现

---

🧠 关键建模思想（教学重点）

这道题可以抽象为：

每个人是一个“点”， a_i 是这个点还能被使用的“度数”， 每次交谈就是 连接两个点的一条边。

目标是： 在度数限制下，构造最多的边，并输出这些边。

---

🧩 常见解题方向

• 贪心思想
• 使用优先队列 / 最大堆
• 每次选择当前“剩余社交度最多”的两个人进行交谈
• 每次消耗两人的社交度各 1
• 重复直到无法再配对

---

🧭 训练的能力点

• 贪心策略建模
• 多重集合 / 堆的使用
• 构造型问题的输出组织
• 将“抽象规则”转化为“图论 / 度数模型”

---