C.Optimal Sorting

选择一段连续区间sort的代价是这段区间的最大值-最小值。求把整个数列sort的最小代价

一整段区间分开sort更优 当且仅当 后面所有数的最小值 > 当前最大值。即产生了一段空隙

因为当前最大值如果大于后面所有数的最小值的话，必然要合并在一起sort。

维护后缀最小值从前向后枚举即可。复杂度 O(n)

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define fr(a) freopen(a, "r", stdin)
#define fo(a) freopen(a, "w", stdout);
#define mod 998244353
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
using namespace std;
const int maxn = 200005;
/**/
int t, n, a[maxn], mi[maxn];
/**/
int main()
{
	// fr("test.in");
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> t;
	while(t--) {
		cin >> n;
		for(int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		mi[n] = a[n];
		for(int i = n - 1; i >= 1; i--) {
			mi[i] = min(mi[i + 1], a[i]);
		}
		int ans = 0, maxnum = 0, minnum = 0x3f3f3f3f;
		mi[n + 1] = INT_MAX;
		for(int i = 1; i <= n; i++) {
			maxnum = max(maxnum, a[i]);
			minnum = min(minnum, a[i]);
			if(mi[i + 1] > maxnum) {
				ans += maxnum - minnum;
				maxnum = 0;
				minnum = 0x3f3f3f3f;
			}
		}
		cout << ans << '\n';
	}
	return 0;
}