https://codeforces.com/contest/2063/problem/B
题目大意
给定某 $n \ (\le 10^5)$ 长的数组 $a \ (1 \le a_i \le 10^9)$ 以及某一个区间 $1 \le l \le r \le n$。进行如下操作一次：
选择 $a$ 的某个子序列，将其拿出来反转之后再放回原位。
问 $sum(l, r)$ 最小是多少。
简要题解
注意到如果 $k$ 长的操作序列最小的 $i_1 < l$ 以及最大的 $i_k > r$ 则这是没必要的，因为显然 $i_1$ 会和 $i_k$ 交换，且这不影响 $sum(l, r)$。因此我们只需要第一个元素 $i_1 < l$ 且 $l \le i_k \le r$ 或 $l \le i_1 \le r$ 且 $r < i_k$ 的。注意 $[l, r]$ 内部与外部选取的元素数量不同也是没有意义的，因为中间的部分交换完相当于还在原来的段。
于是操作相当于任选 $k$ 个在 $[l, r]$ 与任意 $k$ 个 $[1, l - 1]$ 的交换，或者任意 $k$ 个 $[l + 1, n]$ 的交换。我们总是换出尽量大的，换入尽量小的，因此我们对三段排序，再枚举交换多少即可。
复杂度
$T$：$O(n \log n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n, l, r; cin >> n >> l >> r; l--; r--;
vector<int> a(n);
for (int& i : a) cin >> i;
vector<int> la, ma, ra;
for (int i = 0; i < n; i++) {
int v = a[i];
if (i < l) la.push_back(v);
else if (r < i) ra.push_back(v);
else ma.push_back(v);
}
sort(la.begin(), la.end());
sort(ra.begin(), ra.end());
sort(ma.rbegin(), ma.rend());
LL ans = 0;
for (int i : ma) ans += i;
LL cur = ans, tmp = ans;
for (int i = 0; i < (int)min(la.size(), ma.size()); i++) {
cur -= ma[i];
cur += la[i];
cmin(ans, cur);
}
cur = tmp;
for (int i = 0; i < (int)min(ra.size(), ma.size()); i++) {
cur -= ma[i];
cur += ra[i];
cmin(ans, cur);
}
cout << ans << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] E. Collapsing Strings - Educational Codeforces Round 159 (Rated for Div. 2)