题解：CF2074B The Third Side

· · 题解

题目简述

给定长度为 n 的序列 a，每次操作可以选择 a 中的任意两个元素，并选择一个整数 x，使得这三个数可以分别作为一个三角形的边，最后删除 a 中的这两个元素，将 x 添加到 a 中。

重复操作直到 a 中只有一个元素，求这个元素的最大值。

主要思路

小学数学题。要想组成三角形，就要满足两边之和大于第三边。想要最后剩的值最大，x 的选值也要最大，那么 x 就应该选择两数之和减 1。

每次选择两个数，总共就要选择 n-1 次，添加的 x 会让 \sum a 减 1，那么最终答案就是 \sum a-(n-1)。

AC Code

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
typedef long double db;
const int N = 2e5 + 10;
const int INT_INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
// ----------------------------

// ----------------------------

// ----------------------------

int main() {
    int t; cin >> t;
    // ----------------------------
    int n, a, sum;
    while (t--) {
        cin >> n;
        sum = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a;
            sum += a;
        }
        sum -= n - 1;
        cout << sum << '\n';
    }
    return 0;
}