题解：CF2063B Subsequence Update

special_y · 2025-01-23 15:22:08 · 题解

思路

不妨考虑对于下标为 i<l，j>r，此时若交换 i,j 所对应的元素，发现 i,j 交换位置后并不影响区间内的最终输出结果，此时尝试缩小 i,j 的范围，发现最后这样的能交换的子序列一定在区间 [1,r] 或者 [l,n] 中，此时我们只需要拷贝一份数组出来，用开好的两个数组分别排序一侧，这样最后取 r-l+1 的区间长度最小值即可，注意不开 long long 最后会溢出。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t, l, r, n; ll a[100005], b[100005];
int main()
{
    cin.tie(0); cout.tie(0);
    cin >> t;
    for(int i = 1; i <= t; ++i)
    {
       cin >> n >> l >> r;
       memset(a, 0, sizeof(a));
       memset(b, 0, sizeof(b));
       for(int j = 1; j <= n; ++j)
       {
            cin >> a[j];
            b[j] = a[j];
       }
        sort(a+1, a+r+1);
        sort(b+l, b+n+1);
        ll sum1 = 0, sum2 = 0;
        for(int k = 1; k <= r - l + 1; ++k) sum1 += a[k];
        for(int k = l; k <= r; ++k) sum2 += b[k];
        ll minn = min(sum1, sum2);
        cout << minn << endl;
    }
    return 0;
}