7
22
2014
0

3192: [JLOI2013]删除物品

3192: [JLOI2013]删除物品

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 412  Solved: 258
[Submit][Status]

Description

 
箱子再分配问题需要解决如下问题:
 (1)一共有N个物品,堆成M堆。
 (2)所有物品都是一样的,但是它们有不同的优先级。
 (3)你只能够移动某堆中位于顶端的物品。
 (4)你可以把任意一堆中位于顶端的物品移动到其它某堆的顶端。若此物品是当前所有物品中优先级最高的,可以直接将之删除而不用移动。
 
(5)求出将所有物品删除所需的最小步数。删除操作不计入步数之中。
 (6)只是一个比较难解决的问题,这里你只需要解决一个比较简单的版本:
         不会有两个物品有着相同的优先级,且M=2
 

Input

第一行是包含两个整数N1,N2分别表示两堆物品的个数。
接下来有N1行整数按照从顶到底的顺序分别给出了第一堆物品中的优先级,数字越大,优先级越高。
再接下来的N2行按照同样的格式给出了第二堆物品的优先级。
 

Output

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

Sample Input

3 3
1
4
5
2
7
3

Sample Output

6
 

HINT

 

1<=N1+N2<=100000

先ORZ memphis大神http://blog.sina.com.cn/s/blog_c13d10f00101m4sp.html

图有点萎= =

2堆东西头对头合起来,每次移动的距离=当前~分界之间的物品数

然后把当前物品删掉,分界设为当前物品

因为头对头,所以从一堆移到另一堆后合起来的位置是不变的

用树状数组维护物品

代码:好吧好多地方和memphis大神的很像……

#include <cstdio>
#include <algorithm>
using namespace std;
struct node{int data,id;}a[100005];
inline bool cmp(node a,node b){return a.data>b.data;}
int b,c,d,e,f[100005],g,i,j,k,l,m,n,n1,n2,mid;
long long h;
inline int sum(int x){int s=0;for(;x;x-=x&(-x))s+=f[x];return s;}
inline void add(int x,int y){for(;x<=n;x+=x&(-x))f[x]+=y;}
int main(){
    scanf("%d%d",&n1,&n2);
    for(i=n1;i;i--){scanf("%d",&a[i].data);a[i].id=i;}
    for(i=n1+1;i<=n1+n2;i++){scanf("%d",&a[i].data);a[i].id=i;}
    mid=n1;n=n1+n2;
    for(i=1;i<=n;i++)f[i]=1;
    for(i=1;i<=n;i++)if (i+(i&(-i))<=n)f[i+(i&(-i))]+=f[i];
    sort(a+1,a+1+n,cmp);
    for(i=1;i<=n;i++){
        if (mid>=a[i].id)h+=sum(mid)-sum(a[i].id);
        else h+=sum(a[i].id-1)-sum(mid);
        mid=a[i].id;
        add(a[i].id,-1);
    }
    printf("%lld",h);
}
Category: BZOJ | Tags: | Read Count: 796

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com