BZOJ 1106 POI2007 立方体大作战tet 模拟

题目大意：给定一个长度为2n的序列，1~n各出现两次，可以交换相邻两项，两个同样的数放在一起会对消，求把所有数对消的最小交换次数

如果有一对在另一对中间 那么这一对肯定要先于另一对交换

除掉这个因素之外答案是确定的

由于保证交换次数<=100W，因此可以从左向右扫，维护一个栈，按顺序记录还没有被消掉的元素

如果新来的元素在栈里出现过，就直接去栈中查找，删除后直接维护就可以了

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 50500
using namespace std;
int n,ans;
int stack[M],top;
bool v[M];
void Eliminate(int x)
{
	int i;
	for(i=top;i;i--)
		if(stack[i]==x)
			break;
	for(ans+=top-i;i<top;i++)
		stack[i]=stack[i+1];
	top--;
}
int main()
{
	int i,x;
	cin>>n;
	for(i=1;i<=n<<1;i++)
	{
		scanf("%d",&x);
		if(!v[x])
			v[x]=true,stack[++top]=x;
		else
			Eliminate(x);
	}
	cout<<ans<<endl;
	return 0;
}

BZOJ 1106 POI2007 立方体大作战tet 模拟

原文：http://blog.csdn.net/popoqqq/article/details/44180541