题解：AT_abc399_d [ABC399D] Switch Seats

· · 题解

做着题时其实认为比较水，但是不知道同机房的人为什么叫苦连天，废话少说，我们步入正题。

思路解析

首先我们浅浅的分析一下，注意到题目中有提到，答案里的任何一对情侣刚开始都不能坐在一起。
那么两对位置能对答案产生贡献，当且仅当其中能凑出两对情侣，且初始都不坐在一起。
我们要做的就是统计，我们不妨枚举左边的位置，很明显对于一个位置，只有一个对应的位置，我们可以存储第二个数下一次出现的位置。
接下来进行判断贡献，首先判断是否不相邻，然后判断下次出现时是否与第一个数相邻，如果都满足，答案加一。
题目分析完毕，接下来是代码实现。

代码奉上：

AC CODE


#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+5;
const double eps=1e-6;
int n,a[maxn],lst[maxn],t;
signed main(){
    cin>>t;
    while(t--){
        int sum=0;
        cin>>n;
        for(int i=1;i<=2*n;i++){
            cin>>a[i];
            lst[a[i]]=i;
        }
        a[2*n+1]=0;
        for(int i=1;i<2*n;i++){
            if(lst[a[i+1]]<=i+2) continue;
            if(a[lst[a[i+1]]-1]==a[i]||a[lst[a[i+1]]+1]==a[i]) sum++;
        }
        cout<<sum<<endl;
    }
    return 0;
}