程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj3192【JLOI2013】刪除物品

bzoj3192【JLOI2013】刪除物品

編輯:C++入門知識

bzoj3192【JLOI2013】刪除物品


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

6

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;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved