题解：CF2124B Minimise Sum

· · 题解

洛谷CF2124B || CodeForces 2124 B

简要题意

给出一个长度为 n 的数组，保证 \forall i\in[1,n] 都有 0\le a_i\le n。你最多只能对其进行一次操作（也可以选择不操作），选择两个下标 i, j\in[1,n] 且要求 i<j，使 a[i]+=a[j]，之后将 a_j 的值设为 0。请最小化该数组的前缀最小值之和。

思路

考虑到我们可以将 a_j 设为 0，那么 j 之后的所有前缀最小值都会变为 0，那么我们希望 j 的位置尽可能的前。

当然前进是有限度的，我们最前也只能将 j 设为 2，因此对于数组第一项 a_1，其前缀最小值 a_1 是必须要加上的。

若 a_1>a_2，我们不妨令 i=1,j=2，这样 2 以后的所有前缀最小值都会变为 0，那么总答案即为 a_1+a_2。

若 a_1<a_2，那么前缀最小值的第二项仍为 a_1，我们不需要再增加 a_1 了，直接令 i=2,j=3，这样总答案为 a_1\times 2。

容易证明这就是最优解（读者可以尝试思考原因）。

因此，我们得知答案即为 \min(a_1,a_2)+a_1。

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