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,mostlegasked him that how many he had learned. That was really a hard problem, so wy wanted to change to count other things to distractmostleg’s attention. The following problem will tell you what wy counted.
Given2Nintegers in a line, in which each integer in the range from1toNwill 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 first3is in position86and the second3is in position88, you can get 2 marks if you choose to erase3at 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 integerN(1 <= N <= 100000).
The second line:2Nintegers. 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
31 2 3 1 2 331 2 3 3 2 1
Sample Output
69
Hint
We can explain the second sample as this. First, erase1, you get6-1=5marks. Then erase2, you get4-1=3marks. You may notice that in the beginning, the two2s are at positions2and5, but at this time, they are at positions1and4. At last erase3, you get2-1=1marks. Therefore, in total you get5+3+1=9and that is the best strategy.
这道题可以用树状数组做，用map<int,int>hash,来储存相同的数第二次出现的位置，这样待会更新的时候回比较方便，然后这里用到了贪心策略，即依次从左到右进行循环，找出相同的两个数，然后求出两个位置的差，，然后删除这两个位置。
#include<iostream>#include<stdio.h>#include<string.h>#include<math.h>#include<vector>#include<map>#include<queue>#include<stack>#include<string>#include<algorithm>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){map<int,int>hash;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;}
请让我们从容面对这离别之后的离别。
