rt

提交记录

#include <iostream>
using namespace std;
#define int unsigned long long
int t, n;
signed main()
{
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--)
    {
        cin >> n;
        int a[n + 5], sum = 0, maxdepth = 0;
        int lmax[n + 5], rmax[n + 5];
        a[0] = lmax[0] = rmax[n + 1] = 0;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = n; i > 0; i--)
            rmax[i] = max(rmax[i + 1], a[i]);
        for (int i = 1; i <= n; i++)
        {
            lmax[i] = max(lmax[i - 1], a[i]);
            int depth = min(lmax[i], rmax[i]) - a[i];
            sum += depth;
            maxdepth = max(maxdepth, depth);
        }
        int ans = sum - maxdepth;
        for (int l = 1, r = 2; r <= n; l = r, r++)
        {
            int low = lmax[l - 1], s = sum;
            for (; r <= n && a[r] < a[l]; r++)
            {
                low = max(low, a[r]);
                s -= max(0ULL, min(lmax[r], rmax[r]) - low);
            }
            ans = min(ans, s);
        }
        for (int r = n, l = n - 1; l > 0; r = l, l--)
        {
            int low = rmax[r + 1], s = sum;
            for (; l > 0 && a[r] > a[l]; l--)
            {
                low = max(low, a[l]);
                s -= max(0ULL, min(lmax[l - 1], rmax[l + 1]) - low);
            }
            ans = s;
        }
        cout << ans << endl;
    }
    return 0;
}