本文共 1571 字，大约阅读时间需要 5 分钟。

Description

箱子再分配问题需要解决如下问题：

（5）求出将所有物品删除所需的最小步数。删除操作不计入步数之中。

Input

第一行是包含两个整数N1,N2分别表示两堆物品的个数。

Output

对于每个数据，请输出一个整数，即最小移动步数。

Sample Input

3 3

1

4

5

2

7

3

Sample Output

6

HINT

1<=N1+N2<=100000

题解

突然发现把第一组数倒着输入，后一组正着，把顶放在中间，移动的问题就完美解决了。。

比如样例，数组中存5 4 1 2 7 3

移动就是改变分割点，整个操作用树状数组实现。

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;typedef long long LL;const LL N=100005;struct qq{    LL x,id;}a[N];LL f[N];LL n1,n2;LL n;bool cmp (qq a,qq b){  return a.x>b.x;}LL lb (LL x){  return x&(-x);}void change (LL x,LL y){    while (x<=n)    {        f[x]+=y;        x+=lb(x);    }}LL get (LL x){    LL lalal=0;    while (x>=1)    {        lalal=lalal+f[x];        x-=lb(x);    }    return lalal;}int main(){    scanf("%lld%lld",&n1,&n2);    for (LL u=n1;u>=1;u--)    {        scanf("%lld",&a[u].x);        a[u].id=u;    }       for (LL u=1;u<=n2;u++)    {        scanf("%lld",&a[u+n1].x);        a[u+n1].id=u+n1;    }    n=n1+n2;    sort(a+1,a+1+n,cmp);    for (LL u=1;u<=n;u++) change(u,1);    LL ans=0;    a[0].id=n1;    for (LL u=1;u<=n;u++)    {        LL x=a[u-1].id,y=a[u].id;        if (y>x) ans=ans+get(y-1)-get(x);//FYC:y这个点不能算，要减一        else ans=ans+get(x)-get(y);//FYC:这里x不能减一，因为第一次会错，而然后面已近删了没影响        change(y,-1);    }    printf("%lld\n",ans);    return 0;}