题解：AT_abc399_d [ABC399D] Switch Seats

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

思路解析

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

代码奉上：

AC CODE

CPP

#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;
}

题解：AT_abc399_d [ABC399D] Switch Seats

文章操作

思路解析

AC CODE

相关推荐

评论

题解：AT_abc399_d [ABC399D] Switch Seats