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

这道题要求我们操作后奇数与奇数相邻，偶数与偶数相邻，且只有一对奇数与偶数相邻。

很容易想出来，就是让奇数放到一边，偶数放到一边，这样即可满足。

我们贪心的想一下，肯定是保持目前奇数偶数相对位置不变，也就是在前面的去前面，后面的去后面。

由于如果将奇数按策略放到前面可能偶数放到后面就不满足策略。于是对奇数优先排和对偶数优先排得到的答案进行比大小就好了。

注意开 long long

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int cnt,sum,tot,ans;
long long a;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a;
        if(a%2==1){
            cnt++;
            sum+=i-cnt;
        }
        else{
            tot++;
            ans+=i-tot;
        }
    }
    cout<<min(ans,sum);
}

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

文章操作

相关推荐

评论

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