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

player_1_Z · 2025-06-11 11:30:07 · 题解

思路

题目中要求数组奇数和偶数相邻的情况只有一次，所以最后只可能是奇数在一边，偶数在另一边（除非只有奇数或偶数）。那么就好做了，因为只需要看把奇数全部移到左边次数少，还是右边次数少就行了。另外注意，首先这题你不能暴力模拟交换过程，不然会超时，所以我用一个变量 l 存现在这个奇数需要移到的位置，每次更新就行了（具体看代码）。最后再注意一点，这题要开 long long。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000006],ans,ans1,l;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    l=0;//移左 
    for(int i=1;i<=n;i++)
        if(a[i]%2==1){
            ans+=i-l-1;
            l++;//更新
        }
    l=n+1;//移右 
    for(int i=n;i>=1;i--)
        if(a[i]%2==1){
            ans1+=l-i-1;
            l--;//更新 
        }
    cout<<min(ans,ans1);//两种都可以，取最小 
    return 0;
}