首页 > 代码库 > 【BZOJ 3192】 [JLOI2013]删除物品
【BZOJ 3192】 [JLOI2013]删除物品
3192: [JLOI2013]删除物品
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 474 Solved: 293
[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
树状数组,很巧妙的题。
把一堆倒序放在数组中,一堆正序放在他的后面(像是头碰着头)。并记录“头碰头”的交界处为now。
比如样例中的1 4 5 2 7 3在数组中是:5 4 1 2 7 3
然后我们可以惊奇的发现:
想要将位置在i的数取出来,只要把now移到他旁边就行了(相当于把一个堆顶的数移到另一个堆顶);
然后通过前缀和相减求出now移动了几步就是把i取出来要移动的物品数,然后删掉当前取出的数即可!
只要按照物品的优先级从大到小依次循环求出总和就是答案。
前缀和用树状数组维护就可以达到O(nlogn)的复杂度。
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <cmath> #define LL long long using namespace std; int ans,t[200005],n1,n2,n,now; struct data { int p,v; }a[200005]; bool cmp(data a,data b) { return a.v>b.v; } int lowbit(int x) { return x&(-x); } void update(int x,int v) { for (int i=x;i<=n;i+=lowbit(i)) t[i]+=v; } int getsum(int x) { int sum=0; for (int i=x;i;i-=lowbit(i)) sum+=t[i]; return sum; } int query(int a,int b) { if (a>b) swap(a,b); return getsum(b)-getsum(a-1); } int main() { scanf("%d%d",&n1,&n2); n=n1+n2+1; for (int i=n1;i;i--) scanf("%d",&a[i].v); int now=n1+1; for (int i=n1+2;i<=n;i++) scanf("%d",&a[i].v); for (int i=1;i<=n;i++) { if (i!=now) update(i,1); a[i].p=i; } sort(a+1,a+1+n,cmp); LL ans=0LL; for (int i=1;i<n;i++) { ans+=(LL)query(a[i].p,now); ans--; now=a[i].p; update(a[i].p,-1); } printf("%lld\n",ans); return 0; }
感悟:
这个题不是自己想出来的,感觉对于搬动一个堆顶端的数到另一个堆顶的处理十分巧妙,学习之。。
【BZOJ 3192】 [JLOI2013]删除物品
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。