[bzoj3192][JLOI2013]删除物品_树状数组

删除物品 bzoj-3192 JLOI-2013

题目大意：给你n个物品，分成2堆。所有的物品有不同的优先级。我只可以将一堆中的堆顶移动到另一个堆的堆顶。而如果当前物品是全局所有物品中优先级最高的，我可以直接将其删除。询问最小移动多少次，删除不计入总次数。

注释：$1\le n\le 10^5$。

想法：显然是两个栈。开始以为是每个堆中优先级最高的，然后一顿瞎想。如果是全局优先级最高的，就相当于弄两个栈，然后将两个栈顶对顶对到一起，开始指针在两个栈顶之间。那么栈顶的移动就相当于物品的移动。显然答案在序列给出后就是固定的，就是从当前点到整个序列最大值的的有多少个方块隔着，将答案加上即可。而这个找最大值的过程可以用树状数组实现。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cstdlib>

typedef long long ll;

using namespace std;

int n,m,tree[100005];

struct Node

{

	int x,id;

}a[100005];

void del(int x)

{

	for(int i=x;i<=n;i+=(i&(-i)))

		tree[i]--;

}

int getsum(int x)

{

	int t=0;

	for(int i=x;i;i-=(i&(-i))) t+=tree[i]; return t;

}

bool cmp(Node u,Node v)

{

	return u.x>v.x;

}

int main()

{

	scanf("%d%d",&n,&m);

	a[0].id=n;

	for(int i=n;i;i--)

	{

		scanf("%d",&a[i].x);

		a[i].id=i;

	}

	for(int i=1;i<=m;i++)

	{

		scanf("%d",&a[++n].x);

		a[n].id=n;

	}

	sort(a+1,a+n+1,cmp);

	for(int i=1;i<=n;i++)

		tree[i]=(i&(-i));

	ll ans=0;

	for(int i=1;i<=n;i++)

	{

		if(a[i].id>a[i-1].id)

			ans+=getsum(a[i].id-1)-getsum(a[i-1].id);

		else

			ans+=getsum(a[i-1].id)-getsum(a[i].id);

		del(a[i].id);

	}

	printf("%lld\n",ans);

	return 0;

}

小结：这种问题的转化是本质，剩下的实现反而显得平凡。

巴特西

[bzoj3192][JLOI2013]删除物品_树状数组_栈

最新文章

热门文章