题解：CF2129B Stay or Mirror

CR3mPAG · 2026-07-25 16:38:09 · 题解

对于每个位置 i，它的翻转选择只会影响与它相关的可变逆序对：

• 若选择不翻转（a_i = p_i），则 i 与右侧所有满足 p_j < p_i 的位置 j 构成逆序对。
• 若选择翻转（a_i = 2n - p_i），则 i 与左侧所有满足 p_j > p_i 的位置 j 构成逆序对。

需要注意的是，这里的“贡献”指的是原本不是必定逆序对、但因 i 的选择而产生的逆序对数量。

对于每个位置 i，两种选择产生的“额外逆序对”数量分别是：

• 不翻转：右侧小于 p_i 的元素个数；
• 翻转：左侧大于 p_i 的元素个数。

由于每个位置的决策独立影响自己产生的额外逆序对，且互不干扰，因此对每个位置取两种代价的最小值即可得到全局最优解。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3+5;
int t,n,a[N],cnt[N];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],cnt[i]=0;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(a[i]>a[j])
                sum++,cnt[i]++,cnt[j]++;
        }
    }
    for(int i=1;i<=n;i++)
    {
        int p=n-i-cnt[i];
        if(p<0)
            sum+=p;
    }
    cout<<sum<<"\n";
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--)
        solve();
    return 0;
}