3192: [JLOI2013]删除物品
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 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
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);
}
评论 (0)
