CF2227E It All Went Sideways题解

zpy12345 · 2026-08-12 19:45:49 · 题解

我的博客。

感觉使用数据结构单调栈之类的有些复杂了。

首先考虑如果不进行操作，有哪些方块会动。对于同一高度上的一些方块，一定是列下标靠前的一段方块会移动，靠后的一段不会动。如果我们想要使得答案增加，一定要操作靠右不动的那一段方块。

考虑从右到左枚举所有列，设 mx 为当前的后缀列的高度的最小值，那么一定是高度小于等于 mx 的方块不会移动，也就是我们需要操作这一些方块。由于操作是将一个列的高度降低 1，因此我们只需要考虑高度等于 mx 的列中最靠右的列，将其高度减 1。

时间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n,a[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int min1=n+1;
        long long ans=0,sum=0;
        long long max1=0;
        for(int i=n;i>=1;i--)
        {
            if(a[i]<min1) max1=i;
            min1=min(min1,a[i]);
            ans+=a[i]-min1;
            sum=max(sum,max1-i);
        }
        cout<<ans+sum<<"\n";
    }
    return 0;
}