题解：CF2013B Battle for Survive

NEKO_Daze · 2024-10-02 17:59:57 · 题解

洛谷CF2013B || CodeForces 2013 B

简要题意

有一个长度为 n 的数组 a，要进行 n-1 次操作，每次选取两个元素 i,j(1\le i<j\le n)，使 a_j 减少 a_i，然后删除元素 i。请问怎样操作才能使最后剩下的元素值最大？

思路

观察可知 a_{n-1} 的值在最终结果中总是负数，因此，我们可以从 a_{n-1} 中减去总和 a_1 + a_2 + \ldots + a_{n-2}，再从 a_n 中减去 a_{n-1}。然后从 a_n 减去 a_{n-1}。

这样，最后的总和就是 a_1 + a_2 + \ldots + a_{n-2} - a_{n-1} + a_n。由于 a_{n-1} 总是负数，所以不能超过这个值，这就是最大的答案。

记录

#include <bits/stdc++.h>
using namespace std;
int t, n, a[200005];
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        long long sum = 0;
        for (int i = 1; i <= n; i++) {cin >> a[i]; sum += a[i];}
        cout << sum - a[n-1]*2 << endl;
    }
}