专栏文章

题解：CF2124B Minimise Sum

___EM
CF2124B题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miovyzg5
此快照首次捕获于
2025/12/03 02:03
3 个月前
此快照最后确认于
2025/12/03 02:03
3 个月前
查看原文

题目大意：

可以选择两个整数 i,j(i<j)i,j(i<j)。令 ai=ai+aja_i = a_i + a_j，同时令 aj=0a_j = 0。
求 min⁡(a1)+min⁡(a1,a2)+…+min⁡(a1,a2,…,an)\min(a_1) + \min(a_1,a_2) + \ldots + \min(a_1,a_2,\ldots,a_n) 的最小值。

分析：

我们可以用一次机会，使一个数变为 00，另一个数加上这个数原来的值。
因为所有的 aia_i 值均 ≥0\ge 0，所以在 aja_j 变为 00 后，min⁡(a1…aj)\min(a_1\ldots a_j) 至 min⁡(a1…an)\min(a_1\ldots a_n) 均等于 00，满足贪心的要求，aja_j 越前越好，
当 a1>a2a_1 > a_2，我们可以选择 a1a_1 和 a2a_2，此时min⁡(a1)+min⁡(a1,a2)+…+min⁡(a1,a2,…,an)\min(a_1)+\min(a_1,a_2)+\ldots+\min(a_1,a_2,\ldots,a_n) 会等于 a1+a2a_1 + a_2。
当 a1<a2a_1 < a_2，我们可以选择 a2a_2 和 a3a_3 ，但前提为 a1<a2a_1 < a_2，故此时min⁡(a1)+min⁡(a1,a2)+…+min⁡(a1,a2,…,an)\min(a_1)+\min(a_1,a_2)+\ldots+\min(a_1,a_2,\ldots,a_n) 会等于 a1×2a_1 \times 2。
所以答案会等于 min⁡(a1×2,a1+a2)\min(a_1 \times 2,a_1+a_2)

Code

CPP
#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; //好习惯。
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...