选择子序列再逆序

https://codeforces.com/problemset/problem/2063/B

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
using ll = long long;
using pii = pair<int, int>;
const double PI = acos(-1);
const int N =1e5+10;
const int mod = 1e9 + 7;
int a[N];
bool cmp(int x,int y){
	return x>y;
}
void solve(){
	int n,l,r;
	cin>>n>>l>>r;
	vector<int> v,v1,v2;
	ll sum=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(i<l){
			v1.push_back(a[i]);
		}
		else if(i>r){
			v2.push_back(a[i]);
		}
		else {
			v.push_back(a[i]);
			sum+=a[i];
		}
	}
	if(l==1&&r==n) {
		cout<<sum<<endl;
		return;
	}
	sort(v.begin(),v.end(),cmp);
	sort(v1.begin(),v1.end());
	sort(v2.begin(),v2.end());
	ll ans=1e18;
	vector<ll> pre1(l+5),pre(r-l+5),pre2(n-r+5);

	int cnt=1;
	for(auto t:v1){
		pre1[cnt]=pre1[cnt-1]+t;
		cnt++;
	}
	cnt=1;
	for(auto t:v){
		pre[cnt]=pre[cnt-1]+t;
		cnt++;
	}
	cnt=1;
	for(auto t:v2){
		pre2[cnt]=pre2[cnt-1]+t;
		cnt++;
	}
	ll nowsum=sum;
	for(int i=1;i<=min((r-l+1),l-1);i++){
		if(pre1[i]<pre[i]){
			nowsum=sum;
			nowsum-=pre[i];
			nowsum+=pre1[i];
			ans=min(ans,nowsum);
		}
	
	}
	for(int i=1;i<=min((r-l+1),(n-r));i++){
		if(pre2[i]<pre[i]){
			
		nowsum=sum;
		nowsum-=pre[i];
		nowsum+=pre2[i];
		ans=min(ans,nowsum);
		}
	}
	if(ans==1e18){
		ans=sum;
	}
	cout<<ans<<endl;
	
}
int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int T = 1;
	cin>>T;
	while (T--) {
		solve();
	}
	
	return 0;
}

[l,r]中选择一些,ir中再选一些，等价于只在一边1,l-1选比原来少的个数与[l,r]中的一些元素以相同的个数组成最终的子序列，因为个数相同，枚举一下个数就行，[l,r]从大到小排序，1,l-1从小到大排序，分两种情况讨论