程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hoj2430 Counting the algorithms

hoj2430 Counting the algorithms

編輯：關於C++

My Tags (Edit) Source : mostleg Time limit : 1 sec Memory limit : 64 M

Submitted : 725, Accepted : 286

As most of the ACMers, wy's next target is algorithms, too. wy is clever, so he can learn most of the algorithms quickly. After a short time, he has learned a lot. One day, mostleg asked him that how many he had learned. That was really a hard problem, so wy wanted to change to count other things to distract mostleg's attention. The following problem will tell you what wy counted.

Given 2N integers in a line, in which each integer in the range from 1 to N will appear exactly twice. You job is to choose one integer each time and erase the two of its appearances and get a mark calculated by the differece of there position. For example, if the first3 is in position 86 and the second 3 is in position 88, you can get 2 marks if you choose to erase 3 at this time. You should notice that after one turn of erasing, integers' positions may change, that is, vacant positions (without integer) in front of non-vacant positions is not allowed.

Input

There are multiply test cases. Each test case contains two lines.

The first line: one integer N(1 <= N <= 100000).

The second line: 2N integers. You can assume that each integer in [1,N] will appear just twice.

Output

One line for each test case, the maximum mark you can get.

Sample Input

3
1 2 3 1 2 3
3
1 2 3 3 2 1

Sample Output

6
9

Hint

We can explain the second sample as this. First, erase 1, you get 6-1=5 marks. Then erase 2, you get 4-1=3 marks. You may notice that in the beginning, the two 2s are at positions 2 and 5, but at this time, they are at positions 1 and 4. At last erase 3, you get 2-1=1 marks. Therefore, in total you get 5+3+1=9 and that is the best strategy.

這道題可以用樹狀數組做，用maphash,來儲存相同的數第二次出現的位置，這樣待會更新的時候回比較方便，然後這裡用到了貪心策略，即依次從左到右進行循環，找出相同的兩個數，然後求出兩個位置的差，然後刪除這兩個位置。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int a[200006],b[200006],n,vis[200006];
int lowbit(int x){
	return x&(-x);
}
void update(int pos,int num)
{
	while(pos<=2*n){
		b[pos]+=num;pos+=lowbit(pos);
	}
}

int getsum(int pos)
{
	int num=0;
	while(pos>0){
		num+=b[pos];pos-=lowbit(pos);
	}
	return num;
}

int main()
{
	int m,i,j,t,sum;
	while(scanf("%d",&n)!=EOF)
	{
		maphash;
		hash.clear();
		for(i=1;i<=2*n;i++){
			vis[i]=0;
			scanf("%d",&a[i]);
			hash[a[i]]=i;
			b[i]=lowbit(i);
		}
		sum=0;
		for(i=1;i<=2*n;i++){
			if(vis[i]==1)continue;
			vis[i]=1;
			t=hash[a[i]];
			vis[t]=1;
			sum+=getsum(t)-getsum(i);
			update(i,-1);update(t,-1);
			//printf("%d\n",sum);
		}
		printf("%d\n",sum);
	}
	return 0;
}