删除物品 bzoj-3192 JLOI-2013
题目大意：给你n个物品，分成2堆。所有的物品有不同的优先级。我只可以将一堆中的堆顶移动到另一个堆的堆顶。而如果当前物品是全局所有物品中优先级最高的，我可以直接将其删除。询问最小移动多少次，删除不计入总次数。
注释：$1\le n\le 10^5$。
想法：显然是两个栈。开始以为是每个堆中优先级最高的，然后一顿瞎想。如果是全局优先级最高的，就相当于弄两个栈，然后将两个栈顶对顶对到一起，开始指针在两个栈顶之间。那么栈顶的移动就相当于物品的移动。显然答案在序列给出后就是固定的，就是从当前点到整个序列最大值的的有多少个方块隔着，将答案加上即可。而这个找最大值的过程可以用树状数组实现。
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
typedef long long ll;
using namespace std;
int n,m,tree[100005];
struct Node
{
int x,id;
}a[100005];
void del(int x)
{
for(int i=x;i<=n;i+=(i&(-i)))
tree[i]--;
}
int getsum(int x)
{
int t=0;
for(int i=x;i;i-=(i&(-i))) t+=tree[i]; return t;
}
bool cmp(Node u,Node v)
{
return u.x>v.x;
}
int main()
{
scanf("%d%d",&n,&m);
a[0].id=n;
for(int i=n;i;i--)
{
scanf("%d",&a[i].x);
a[i].id=i;
}
for(int i=1;i<=m;i++)
{
scanf("%d",&a[++n].x);
a[n].id=n;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
tree[i]=(i&(-i));
ll ans=0;
for(int i=1;i<=n;i++)
{
if(a[i].id>a[i-1].id)
ans+=getsum(a[i].id-1)-getsum(a[i-1].id);
else
ans+=getsum(a[i-1].id)-getsum(a[i].id);
del(a[i].id);
}
printf("%lld\n",ans);
return 0;
}
小结：这种问题的转化是本质，剩下的实现反而显得平凡。