程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> bzoj3192【JLOI2013】刪除物品

bzoj3192【JLOI2013】刪除物品

編輯：關於C++

3192: [JLOI2013]刪除物品

Time Limit:10 SecMemory Limit:128 MB
Submit:747Solved:441
[Submit][Status][Discuss]

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

HINT

1<=N1+N2<=100000

模擬水題，樹狀數組維護一下。

#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 100005
using namespace std;
int n,n1,n2,tmp;
int a[maxn],b[maxn],f[maxn],s[maxn];
ll ans;
map mp;
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;
}
inline void change(int x)
{
	for(;x<=n;x+=(x&(-x))) s[x]++;
}
inline int query(int x)
{
	int ret=x;
	for(;x;x-=(x&(-x))) ret-=s[x];
	return ret;
}
int main()
{
	n1=read();n2=read();n=n1+n2;
	D(i,n1,1) a[i]=read();
	F(i,n1+1,n) a[i]=read();
	F(i,1,n) mp[a[i]]=i,b[i]=a[i];
	sort(b+1,b+n+1);
	F(i,1,n) a[mp[b[i]]]=i;
	F(i,1,n) f[a[i]]=i;
	tmp=n1;
	D(i,n,1)
	{
		int pos=query(f[i]);
		if (pos>tmp) ans+=pos-(tmp+1);
		else ans+=tmp-pos;
		tmp=pos-1;
		change(f[i]);
	}
	printf("%lld\n",ans);
	return 0;
}