题解归档 - cf2227E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2227E
• 本地来源：problems/cf2227E/idea.md
• 题目链接：https://codeforces.com/contest/2227/problem/E
• 原始标题：cf2227E - It All Went Sideways

思路

cf2227E - It All Went Sideways

pattern: row compaction counted by suffix minima.

claim: for a fixed height h, cubes that do not move are exactly the trailing occupied suffix in that row. Summing over all heights, the number of unmoved cubes is sum_i min(a_i..a_n). Thus the initial moved count is sum(a) - sum(suffix_min).

single decrease: decreasing a_p by 1 lowers exactly those suffix minima suffix_min[i] with i <= p and suffix_min[i] == a_p. If this count is d, total cubes drops by 1 and fixed cubes drops by d, so the moved count improves by d - 1.

algorithm: scan left to right, maintain frequencies of suffix_min[i] among processed positions, and maximize freq[a[p]].

check: brute row simulation on random small arrays.

代码

来源：problems/cf2227E/solution.cpp

/* Author: likely
 * Time: 2026-06-27
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int>a(n+2),suf(n+3);
        ll total=0,fixed=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            total+=a[i];
        }
        suf[n+1]=n+1;
        for(int i=n;i>=1;i--){
            suf[i]=min(a[i],suf[i+1]);
            fixed+=suf[i];
        }
        vector<int> freq(n+2,0);
        int best=0;
        for(int i=1;i<=n;i++){
            freq[suf[i]]++;
            best=max(best,freq[a[i]]);
        }
        ll ans=total-fixed+max(0,best-1);
        cout<<ans<<"\n";
    }
    return 0;
}