题解：CF2124B Minimise Sum

__EM · 2025-07-15 12:31:09 · 题解

题目大意：

可以选择两个整数 i,j(i<j)。令 a_i = a_i + a_j，同时令 a_j = 0。

求 \min(a_1) + \min(a_1,a_2) + \ldots + \min(a_1,a_2,\ldots,a_n) 的最小值。

分析：

我们可以用一次机会，使一个数变为 0，另一个数加上这个数原来的值。

因为所有的 a_i 值均 \ge 0，所以在 a_j 变为 0 后，\min(a_1\ldots a_j) 至 \min(a_1\ldots a_n) 均等于 0，满足贪心的要求，a_j 越前越好，

当 a_1 > a_2，我们可以选择 a_1 和 a_2，此时\min(a_1)+\min(a_1,a_2)+\ldots+\min(a_1,a_2,\ldots,a_n) 会等于 a_1 + a_2。

当 a_1 < a_2，我们可以选择 a_2 和 a_3 ，但前提为 a_1 < a_2，故此时\min(a_1)+\min(a_1,a_2)+\ldots+\min(a_1,a_2,\ldots,a_n) 会等于 a_1 \times 2。

所以答案会等于 \min(a_1 \times 2,a_1+a_2)

Code

#include<bits/stdc++.h>
using namespace std;
int n,a,b,t,c;  //c用来存放无用的数字。
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>a>>b;
        for(int i=3;i<=n;i++)
            cin>>c;
        cout<<min(a*2,a+b)<<"\n";  // 直接计算。
    }
    return 0; //好习惯。
}