专栏文章

题解：CF2124B Minimise Sum

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mioxlefm
此快照首次捕获于
2025/12/03 02:48
3 个月前
此快照最后确认于
2025/12/03 02:48
3 个月前
查看原文
洛谷CF2124B || CodeForces 2124 B

简要题意

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

思路

考虑到我们可以将 aja_j 设为 00，那么 jj 之后的所有前缀最小值都会变为 00，那么我们希望 jj 的位置尽可能的前。
当然前进是有限度的，我们最前也只能将 jj 设为 22，因此对于数组第一项 a1a_1，其前缀最小值 a1a_1 是必须要加上的。
若 a1>a2a_1>a_2，我们不妨令 i=1,j=2i=1,j=2，这样 22 以后的所有前缀最小值都会变为 00，那么总答案即为 a1+a2a_1+a_2。
若 a1<a2a_1<a_2，那么前缀最小值的第二项仍为 a1a_1，我们不需要再增加 a1a_1 了，直接令 i=2,j=3i=2,j=3，这样总答案为 a1×2a_1\times 2。
容易证明这就是最优解（读者可以尝试思考原因）。
因此，我们得知答案即为 min⁡(a1,a2)+a1\min(a_1,a_2)+a_1。
CPP
#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;
    }
}

评论

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

正在加载评论...