Codeforces Round 1009 (Div. 3)：B. The Third Side ——Thinking

#	User	Rating
1	jiangly	3845
2	tourist	3798
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3589
6	Ormlis	3532
7	Benq	3468
8	Radewoosh	3463
9	ecnerwala	3451
10	Um_nik	3450

#	User	Contrib.
1	cry	165
2	Qingyu	159
2	-is-this-fft-	159
4	atcoder_official	157
5	Dominater069	156
6	adamant	154
7	djm03178	151
8	luogu_official	150
9	awoo	148
10	TheScrasse	145

我将详细分析这个问题，推导其数学规律，并解释为什么你的代码可以正确求解序列 (a) 中最后一个元素的最大可能值。

一、问题分析

问题描述

给定一个由 (n) 个正整数组成的序列 (a)。
每次操作：

选择两个不同索引 (i) 和 (j)。
选择一个正整数 (x)，使得 (a_i)、(a_j)、(x) 能组成一个**非退化三角形**（即满足三角形三边不等式：(a_i + a_j > x)、(a_i + x > a_j)、(a_j + x > a_i)）。
删除 (a_i) 和 (a_j)，将 (x) 追加到序列末尾。

重复操作直到序列只剩 1 个元素。
目标：求最后一个元素的最大可能值。

关键点

非退化三角形条件：
(a_i + a_j > x)。
(a_i + x > a_j)（等价于 (x > a_j — a_i)）。
(a_j + x > a_i)（等价于 (x > a_i — a_j)）。
假设 (a_i \geq a_j)，则：
- (x > a_i — a_j)。
- (x < a_i + a_j)。
(x) 的取值范围：(a_i — a_j < x < a_i + a_j)。
序列变化：
每次操作减少 1 个元素（移除 2 个，添加 1 个），从长度 (n) 变为 (n-1)、(n-2)、...、1）。
总操作次数为 (n-1) 次。
最大值目标：
每次选择 (x) 时，尽量取最大值（接近 (a_i + a_j)），以使最后剩下的元素尽可能大。

二、数学推导

观察操作的影响

每次操作用 (x) 替换 (a_i) 和 (a_j)。
(x) 的最大可能值接近 (a_i + a_j)（但需满足 (x < a_i + a_j) 且为正整数）。
设初始序列总和为 (S = a_1 + a_2 + \cdots + a_n)。
每次操作后，序列总和变为 (S — a_i — a_j + x = S — (a_i + a_j — x))。
定义 (d = a_i + a_j — x)（移除的“差值”），则：
(d > 0)（因为 (x < a_i + a_j)）。
总和减少 (d)。

总和变化

初始总和：(S)。
经过 (n-1) 次操作，序列剩 1 个元素，设最后值为 (R)。
每次操作减少一个 (d_k)（第 (k) 次操作的差值），总减少量为 (D = d_1 + d_2 + \cdots + d_{n-1})。
则：(R = S — D)。
(D) 的最小值为多少？最大化 (R) 等价于最小化 (D)。

最小化 (D)

(d_k = a_i + a_j — x)。
(x) 的最大值为 (a_i + a_j — 1)（因为 (x < a_i + a_j) 且 (x) 是正整数）。
因此，(d_k) 的最小值为：
(d_k = a_i + a_j — (a_i + a_j — 1) = 1)。
如果每次操作都能取 (x = a_i + a_j — 1)：
(D = d_1 + d_2 + \cdots + d_{n-1} = 1 \cdot (n-1) = n-1)。
(R = S — D = S — (n-1))。

可行性验证

是否每次都能取 (x = a_i + a_j — 1)？
检查三角形条件：
- (a_i + a_j > x)。
- (a_i + x > a_j)。
- (a_j + x > a_i)。
代入 (x = a_i + a_j — 1)：
- (a_i + a_j > a_i + a_j — 1)：成立。
- (a_i + (a_i + a_j — 1) > a_j)：(2a_i + a_j — 1 > a_j)，即 (2a_i > 1)，因为 (a_i \geq 1)，成立。
- (a_j + (a_i + a_j — 1) > a_i)：(a_j + a_i + a_j — 1 > a_i)，即 (2a_j > 1)，因为 (a_j \geq 1)，成立。
结论：对于任意正整数 (a_i, a_j)，(x = a_i + a_j — 1) 总能组成非退化三角形。

最大值公式

(D_{\text{min}} = n-1)。
(R_{\text{max}} = S — (n-1) = S — n + 1)。
你的代码输出：(sum + 1 — n)，即 (S — n + 1)。

三、为什么代码正确

代码分析

#include <iostream>
using namespace std;

int t, n;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> t;
    while (t--) {
        cin >> n;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int a;
            cin >> a;
            sum += a;
        }
        cout << sum + 1 - n << endl;
    }
    return 0;
}