[BZOJ1106] [POI2007]立方体大作战tet

本文主要是介绍[BZOJ1106] [POI2007]立方体大作战tet，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

http://www.lydsy.com/JudgeOnline/problem.php?id=1106

题目大意

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

题解

如果一对在另一对内部,那么先消掉它,所以我们用一个栈存,如果这个数在栈中,那么把他们内部的部分向前移即可
由于ans不超过1000000所以暴力即可

varx,t:array[0..50005]of longint;i,j,k:longint;n,ans:longint;
procedure swap(var a,b:longint);
var c:longint;
beginc:=a; a:=b; b:=c;
end;beginreadln(n); ans:=0;fillchar(x,sizeof(x),0); t[0]:=0;for i:=1 to 2*n dobegininc(t[0]); readln(t[t[0]]);if x[t[t[0]]]=0then x[t[t[0]]]:=1else beginfor j:=t[0]-1 downto 1 doif t[j]=t[t[0]] then break;inc(ans,t[0]-j-1);for k:=j to t[0]-1 dot[k]:=t[k+1];dec(t[0],2);end;end;writeln(ans);
end.

这篇关于[BZOJ1106] [POI2007]立方体大作战tet的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---