题目描述
箱子再分配问题需要解决如下问题：
（1）一共有N个物品，堆成M堆。
（2）所有物品都是一样的，但是它们有不同的优先级。
（3）你只能够移动某堆中位于顶端的物品。
（4）你可以把任意一堆中位于顶端的物品移动到其它某堆的顶端。若此物品是当前所有物品中优先级最高的，可以直接将之删除而不用移动。
（5）求出将所有物品删除所需的最小步数。删除操作不计入步数之中。
（6）只是一个比较难解决的问题，这里你只需要解决一个比较简单的版本：
不会有两个物品有着相同的优先级，且M=2
输入
第一行是包含两个整数N1,N2分别表示两堆物品的个数。
接下来有N1行整数按照从顶到底的顺序分别给出了第一堆物品中的优先级，数字越大，优先级越高。
再接下来的N2行按照同样的格式给出了第二堆物品的优先级。
输出
对于每个数据，请输出一个整数，即最小移动步数。
样例输入
3 3
1
4
5
2
7
3
样例输出
6
提示
1<=N1+N2<=100000
题解
讲个真实的故事：说从前有个小傻瓜，她打了一个50分的模拟，但她对这个模拟很不满意，认为它T得太厉害。后来她想到了一个60分的优化方法，于是她打了出来，又把它交了上去，但是这个优化有个小缺陷，然后0分。。。明明是一道很清楚的题啊。今天考完试之后，似乎有很多同学觉得自己离正解和高分很近，然而结果却很糟，我不也是这样吗？虽然这样的事很可惜，可是事出有因。好多数据结构很久没打过，早上稍微看了一下树状数组，但是没有细致复习，总觉得打线段树也是一样(这代码量根本没法比)。甚至于改完了之后在cogs上提交，因为太急躁三遍都没打对文件名，这就是心态问题了。吃一堑长一智，不是但愿如此，而是必须如此。
int lowbit(int x)
{
return x&(-x);
}
for(int i=1;i<=n;i++)
{
int temp=lowbit(i);
for(int j=i-t+1;j<=i;j++)
d[i]+=a[j];
}
int getsum(int x)
{
int jg=0;
while(x>0)
{
jg+=d[x];
x-=lowbit(x);
}
return jg;
}
void update(int x,int y)
{
while(x<=n)
{
d[x]+=y;
x+=lowbit(x);
}
}
先把物品的优先级离散一下，再把第一堆倒序和第二堆对在一起，标记出各优先级的物品所在的位置，然后用树状数组处理；优先级最高的物品特殊处理，此后每个物品到下一个物品的步数等于两物品前缀和之差的绝对值-1，每移动一个物品就把它的权值变为0即可。
for(int i=n;i>1;i--)
{
jg+=abs(getsum(wz[i])-getsum(wz[i-1]))-1;
update(wz[i],-1);
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int sj=;
int n1,n2,n,yx[sj],a1,a2,wz[sj],a[sj],d[sj],t;
long long jg;
struct WP
{
int ord;
long long vl;
}wp[sj];
int comp(const WP&a,const WP&b)
{
return a.vl<b.vl;
}
int lowbit(int x)
{
return x&(-x);
}
int getsum(int x)
{
int res=;
while(x>)
{
res+=d[x];
x-=lowbit(x);
}
return res;
}
void update(int x,int y)
{
while(x<=n)
{
d[x]+=y;
x+=lowbit(x);
}
}
int main()
{
scanf("%d%d",&n1,&n2);
n=n1+n2;
for(int i=;i<=n;i++)
{
scanf("%lld",&wp[i].vl);
wp[i].ord=i;
}
sort(wp+,wp+n+,comp);
for(int i=;i<=n;i++)
yx[wp[i].ord]=i;
for(int i=;i<=n1;i++)
{
a[n1-i+]=;
wz[yx[i]]=n1-i+;
}
for(int i=n1+;i<=n;i++)
{
a[i]=;
wz[yx[i]]=i;
}
if(wz[n]>n1) jg=wz[n]-n1-;
else jg=n1-wz[n];
for(int i=;i<=n;i++)
{
t=lowbit(i);
for(int j=i-t+;j<=i;j++)
d[i]+=a[j];
}
for(int i=n;i>;i--)
{
jg+=abs(getsum(wz[i])-getsum(wz[i-]))-;
update(wz[i],-);
}
printf("%lld",jg);
//while(1);
return ;
}