「BZOJ3192」[JLOI2013] 删除物品
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
题解
将两堆放在一起，设分界点为mid。由于删除时只能按照编号降序依次删除，则首先将数字排序并记录数字的位置。从大到小删除。根据每个数字的位置计算删除每个数字的移动次数。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n1,n2,n,now; int t[100005]; ll ans; struct data{int v,p;}a[100005]; inline bool operator<(data a,data b) { return a.v>b.v; } inline int lowbit(int x) { return x&(-x); } void add(int x,int v) { for(int i=x;i<=n;i+=lowbit(i)) t[i]+=v; } int que(int x) { int sum=0; for(int i=x;i;i-=lowbit(i)) sum+=t[i]; return sum; } inline int query(int a,int b) { if(a>b)swap(a,b); return que(b)-que(a-1); } int main() { n1=read();n2=read();n=n1+n2+1; for(int i=n1;i;i--)a[i].v=read(); for(int i=n1+2;i<=n;i++)a[i].v=read(); now=n1+1; for(int i=1;i<=n;i++) { if(i!=now)add(i,1); a[i].p=i; } sort(a+1,a+n+1); for(int i=1;i<n;i++) { ans+=query(a[i].p,now)-1; now=a[i].p;add(now,-1); } printf("%lld",ans); return 0; } |
Subscribe
计数器 9855274
OI 课件=>
OI 课件=>