标签：贪心，栈
题目
Description
一个叫做立方体大作战的游戏风靡整个Byteotia。这个游戏的规则是相当复杂的，所以我们只介绍他的简单规 则：给定玩家一个有2n个元素的栈，元素一个叠一个地放置。这些元素拥有n个不同的编号，每个编号正好有两个 元素。玩家每次可以交换两个相邻的元素。如果在交换之后，两个相邻的元素编号相同，则将他们都从栈中移除， 所有在他们上面的元素都会掉落下来并且可以导致连锁反应。玩家的目标是用最少的步数将方块全部消除。 Input
第一行包含一个正整数n(1<=n<=50000)。接下来2n行每行一个数ai，从上到下描述整个栈，保证每个数出现且 仅只出现两次(1<=ai<=n)。初始时，没有两个相同元素相邻。并且保证所有数据都能在1000000步以内出解。 Output
第一行包含一个数m，表示最少的步数。 Sample Input 样例输入1
5
5
2
3
1
4
1
4
3
5
2
样例输入2
3
1
2
3
1
2
3
Sample Output 样例输出1
2
样例输出2
3
分析
对于12XXXX21这种形式的序列来说，我们合并2一定比合并1更优，所以对于嵌套关系的先删去中间的那对最优
对于12XX12这样相交关系的序列来说，合并1和2对答案不会产生影响
这样的贪心很显然是正确的
然后就维护一个栈解决
这题在洛谷上也有P3460，但是多了一问要输出方案
调了一整天都没A掉输出方案的版本（我题意理解错了）
输出方案是重新构成的序列中的位置
然而我自己写spj感觉应该是原序列中的位置（因为检验重新构成的序列中的位置spj版本不好写啊，或许是我太弱）
有没有大佬还看下那道题，欢迎下面评论啊
终于A掉这题了（洛谷上带有方案的版本）
这题spj原来要用平衡树/链表+线段树 写
zyl说这是全站第三难写的spj orz
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e5+6;
int a[maxn],vis[maxn],top=0,ans=0,cnt=0,n;
struct node{int val,pos;}s[maxn];
int main()
{
n=read();
rep(i,1,2*n){
int x=read();
if(!vis[x]){vis[x]=1;s[++top].val=x;s[top].pos=i;}
else{
int k=0;
dep(j,top,1)
if(s[j].val==x){k=j;break;}
ans+=top-k;if(top!=k)a[++cnt]=s[k].pos;top--;
//cout<<k<<' '<<top<<' '<<ans<<endl;
rep(j,k,top)s[j]=s[j+1];
}
}
printf("%d\n",ans);
//rep(i,1,cnt)printf("%d\n",a[i]);
return 0;
}
