题解：P12688 [KOI 2022 Round 1] 避开

K_yuxiang_rose · 2025-06-06 21:56:36 · 题解

「奇数与偶数相邻的情况最多只出现一次」实际上就是把奇数和偶数分开，那么只需要判断将奇数放在左边更优还是把偶数放在左边更优即可。

显然奇数与奇数，或偶数与偶数之间不需要交换，所以只需要统计当前奇数（或偶数）的出现次数，判断前面有几个位置已经被奇数（或偶数）占了，就能够求出操作步数了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int n,cnt1=0,cnt2=0,sum1=0,sum2=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(x%2) cnt1++,sum1+=(i-cnt1);
        else cnt2++,sum2+=(i-cnt2);
    }
    cout<<min(sum1,sum2);
    return 0;
}
```