CF2107F1

HasNoName · 2025-09-23 16:39:53 · 题解

思路

感觉这题的难度是严重高评的，实际难度应该只有黄，20 分钟是绝对可以过的。

考虑贪心。

考虑如果他在 i 后面（i>1），且 a_{i-1}<a_i，则交换 a_{i-1} 和 a_i 一定不劣。

所以考虑如果将 a_1 与后面的一项交换后然后再顺序枚举一遍即可。

正确性显然。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int a[N],b[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T,n;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        reverse(a+1,a+n+1);
        long long aans=1e18;
        for(int id=1;id<=n;id++)
        {
            for(int i=1;i<=n;i++)b[i]=a[i];
            swap(b[1],b[id]);
            long long ans=id-1+b[1];
            for(int i=2;i<=n;i++)
            {
                if(b[i]>b[i-1])
                {
                    swap(b[i],b[i-1]);
                    ans++;
                }
                ans+=b[i];
            }
            aans=min(ans,aans);
        }
        cout<<aans<<'\n';
    }
    return 0;
}