HOJ 2430——Counting the algorithms（樹狀數組+貪心）

 

Counting the algorithms

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

Submitted : 701, Accepted : 273

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 first 3 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=1marks. Therefore, in total you get 5+3+1=9 and that is the best strategy.

 

 

————————————————————分割線——————————————————

題目大意：

給定2n個整數，范圍為1到n，每個數出現兩次，每個數都有一個下標，每次刪除兩個相同的數，能獲得下標差的值，求這個值得最大

 

思路：

對於相間的情況，從外圍往內刪跟從內往外刪是一樣的，而對於 包含的情況，從外往內刪是最優的。因此，選擇從外往內刪。

具體操作：

掃描一次，記錄每個數第二次出現的下標，將數的下標插人樹狀數組。然後從左往右或者從右往左掃描，那麼值為兩個數的距離差，之後刪除其中一個數，如果是從左往右掃描的，則刪除第二次出現的下標，如果是從右往左掃描的，則刪除第一次出現的下標

 

 

 

#include
#include
#include
#define ll long long
#define M 200000+10
using namespace std;
int a[M],c[M],f[M];
bool judge[M];
int n;
void update(int x,int v)
{
    for(int i=x;i<=2*n;i+=i&-i){
        c[i]+=v;
    }
}
int getsum(int x)
{
    int sum=0;
    for(int i=x;i>0;i-=i&-i){
        sum+=c[i];
    }
    return sum;
}
int main()
{
    while(scanf("%d",&n)!=EOF){
        memset(judge,false,sizeof(judge));
        memset(c,0,sizeof(c));
        memset(f,0,sizeof(f));
        for(int i=1;i<=2*n;++i){
            scanf("%d",&a[i]);
            update(i,1);
            if(!judge[a[i]]) judge[a[i]]=true;
            else f[a[i]]=i;
        }
        int sum=0;
        for(int i=1;i<=2*n;++i){
            sum+=getsum(f[a[i]])-getsum(i);
            update(f[a[i]],-1);
        }
        printf("%d\n",sum);
    }
    return 0;
}