题意：

给定玩家一个有2n个元素的栈，这些元素拥有n个不同的编号，每个编号正好有两个元素。玩家每次可以交换两个相邻的元素。如果在交换之后，两个相邻的元素编号相同，则将他们都从栈中移除，所有在他们上面的元素都会掉落下来并且可以导致连锁反应。求最少的步数将方块全部消除。

题解：

用一个栈维护，如果遇到一个没有遇到过的编号就入栈，否则就让之前的那个元素出栈，两个元素之间的元素向下移一位，并将两个元素的距离计入答案。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 100010 6 using namespace std; 7  8 inline int read(){ 9     char ch=getchar(); int f=1,x=0;10     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}11     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();12     return f*x;13 }14 int st[maxn],top,ans,n; bool in[maxn];15 int main(){16     n=read();17     inc(i,1,2*n){18         int x=read();19         if(!in[x])in[x]=1,st[++top]=x;else{20             int j=top; while(st[j]!=x)j--; inc(k,j,top-1)st[k]=st[k+1],ans++; top--; in[x]=0;21         }22     }23     printf("%d",ans); return 0;24 }
       
      
     

 

20160810