传送门：洛谷 CF2074B The Third Side | Codeforces B. The Third Side

更佳的阅读体验：CF2074B 题解

简要题意：给定序列 $a$，需要重复进行操作，直到 $a$ 中仅剩一个元素：选择 $a$ 中的任意两个元素，并指定一个正整数 $x$，使得这两个元素与 $x$ 可以构成三角形，然后从 $a$ 中删除选定的两个元素，并将 $x$ 插入 $a$ 末尾。求出这个剩下的元素的最大值。

首先需要考虑一个问题，什么情况下剩下的那个值可以最大？可以想到，我们需要贪心地保证每次插入的数都尽可能大才行。

接下来就需要考虑怎么求这个最大的数。

假设三角形的三条边为 $x$、$y$ 和 $z$，那么就有：

$$ \begin{cases} x + y > z \\ x + z > y \\ y + z > x \end{cases} $$

我们假设从序列中取出的两个数是 $x$ 和 $y$，那么此时就需要最大化 $z$ 的值。我们首先考虑 $x + y > z$，显然有 $z \le x + y - 1$，即 $z$ 最大可以取到 $x + y - 1$。

我们将 $z = x + y - 1$ 代入其它两个式子，有：

$$ \begin{cases} x + (x + y - 1) > y \\ y + (x + y - 1) > x \end{cases} \ \Longrightarrow \ \begin{cases} 2x - 1 > 0 \\ 2y - 1 > 0 \end{cases} $$

由于 $x, y \ge 1$，上式显然成立，得证。此时我们想到，只需要每次取出 $a$ 中最小的两个数 $x, y$，然后将 $x + y - 1$ 重新插入即可。

我们可以使用 priority_queue 来维护上述操作。每次取出堆顶的两个数，并插入一个新的数，直到堆中只剩一个元素，输出即可。

#include <iostream>
#include <queue>
using namespace std;

const int N = 2e5 + 10;
int t, n, a, x, y;
priority_queue<int> q;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        while (!q.empty()) q.pop();
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a, q.emplace(a);
        while (q.size() > 1) {
            x = q.top();
            q.pop();
            y = q.top();
            q.pop();
            q.emplace(x + y - 1);
        } cout << q.top() << '\n';
    } return 0;
}