BZOJ3192：[JLOI2013]删除物品—

BZOJ3192：[JLOI2013]删除物品——题解

阅读量：6496 次

发布时间：2019-06-24

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

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

（1）一共有N个物品，堆成M堆。

（2）所有物品都是一样的，但是它们有不同的优先级。

（3）你只能够移动某堆中位于顶端的物品。

（4）你可以把任意一堆中位于顶端的物品移动到其它某堆的顶端。若此物品是当前所有物品中优先级最高的，可以直接将之删除而不用移动。

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

（6）只是一个比较难解决的问题，这里你只需要解决一个比较简单的版本：不会有两个物品有着相同的优先级，且M=2

水题，注意开longlong。

把两个栈口对口连上，然后每次记录当前的栈口在哪两个元素之间，按照元素大小顺序依次找要被删掉的数的位置，之后就分类讨论即可。

注意记录一下哪些位置的数被删掉了就好，树状数组维护即可。

#include#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;typedef long long ll;const int N=2e5+5;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct node{ int x,y;}b[N];int n,m,a[N],tr[N];inline bool cmp(node a,node b){ return a.x>b.x;}inline int lowbit(int t){ return t&-t;}inline void add(int x,int y){ for(int i=x;i<=n;i+=lowbit(i))tr[i]+=y;}inline int ask(int x){ int res=0; for(int i=x;i;i-=lowbit(i))res+=tr[i]; return res;}int main(){ n=read(),m=read(); for(int i=n;i>=1;i--){ a[i]=b[i].x=read(); b[i].y=i; } for(int i=n+1;i<=n+m;i++){ a[i]=b[i].x=read(); b[i].y=i; } int l=n;ll ans=0;n+=m; sort(b+1,b+n+1,cmp); for(int i=1;i<=n;i++){ int t=b[i].y; if(t<=l){ ans+=l-t-ask(l)+ask(t-1); }else{ ans+=t-l-ask(t)+ask(l)-1; } l=t-1; add(t,1); } printf("%lld\n",ans); return 0;}