思路

不妨考虑对于下标为

i<l

，

j>r

，此时若交换

i,j

所对应的元素，发现

i,j

交换位置后并不影响区间内的最终输出结果，此时尝试缩小

i,j

的范围，发现最后这样的能交换的子序列一定在区间

[1,r]

或者

[l,n]

中，此时我们只需要拷贝一份数组出来，用开好的两个数组分别排序一侧，这样最后取

r-l+1

的区间长度最小值即可，注意不开 long long 最后会溢出。

代码

CPP

#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;
}

CPP

题解：CF2063B Subsequence Update

文章操作

思路

代码

相关推荐

评论

题解：CF2063B Subsequence Update