题解：AT_abc399_d [ABC399D] Switch Seats

Emplace · 2025-03-30 09:03:15 · 题解

思路

性质

我们可以发现，只有相邻两个数满足条件，且不能相等，并且两个数都不能与旁边的数相等。它们对应的数也是这样。

做法

记录每个数出现的两次位置。然后对于每个数，只需要求它的另外一个数与它下一个数的另外一个数即可，然后按照性质判断即可。

Code

#include<bits/stdc++.h>
using namespace std;
int t,n,a[500000],cnt,t1[500000],t2[500000];
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=2*n;i++) t1[i]=0,t2[i]=0;
        for(int i=1;i<=2*n;i++){
            cin>>a[i];
            if(!t1[a[i]]) t1[a[i]]=i;
            else t2[a[i]]=i;
        }
        cnt=0;
        for(int i=1;i<=2*n-1;i++){
            int j,k;
            if(t1[a[i]]==i) j=t2[a[i]];
            else j=t1[a[i]];
            if(t1[a[i+1]]==i+1) k=t2[a[i+1]];
            else k=t1[a[i+1]];
            if(abs(k-j)==1&&abs(j-i)>1&&abs(k-i-1)>1){
                cnt++;
            }
        }
        cout<<cnt/2<<endl;
    }
    return 0;
}