hdu 2838 Cow Sorting (樹狀數組)

Cow Sorting

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2185    Accepted Submission(s): 683

Problem Description Sherlock's N (1 ≤ N ≤ 100,000) cows are lined up to be milked in the evening. Each cow has a unique "grumpiness" level in the range 1...100,000. Since grumpy cows are more likely to damage Sherlock's milking equipment, Sherlock would like to reorder the cows in line so they are lined up in increasing order of grumpiness. During this process, the places of any two cows (necessarily adjacent) can be interchanged. Since grumpy cows are harder to move, it takes Sherlock a total of X + Y units of time to exchange two cows whose grumpiness levels are X and Y.

Please help Sherlock calculate the minimal time required to reorder the cows.  

Input Line 1: A single integer: N

Lines 2..N + 1: Each line contains a single integer: line i + 1 describes the grumpiness of cow i.  

Output Line 1: A single line with the minimal time required to reorder the cows in increasing order of grumpiness.  

Sample Input 3 2 3 1  

Sample Output 7   Hint Input Details Three cows are standing in line with respective grumpiness levels 2, 3, and 1. Output Details 2 3 1 : Initial order. 2 1 3 : After interchanging cows with grumpiness 3 and 1 (time=1+3=4). 1 2 3 : After interchanging cows with grumpiness 1 and 2 (time=2+1=3).  

Source 2009 Multi-University Training Contest 3 - Host by WHU  

Recommend gaojie   |   We have carefully selected several similar problems for you:   3450  2227  3030  2642  2836   

題意：

    求逆序數兩兩的總和： 如 3 2 1 ：sum=(3+2)+(3+1)+(2+1)=12;   1 2 3: sum=0;

樹狀數組：

    其實這題并不難，抓住一個點和熟悉樹狀數組大概就可以做出來了，那個點就是如何求得和。

    這裡才用的方法是參考别人的 ，自己想了一段時間沒想出來。

    對于新插入的一個元素，運用樹狀數組，可以求得比它小的元素的個數，比它小的元素的和，在它之前的元素的總和。

    而對于每一個新元素，其sum[m]=m*(比它大的元素個數)+(前i個元素的和)-(比它小的元素的和)。

    然後累加得解。

實作：

1 //46MS    2584K    955 B    C++
 2 #include<stdio.h>
 3 #include<string.h>
 4 #define ll __int64
 5 #define N 100005
 6 ll cnt[N],ssum[N],tsum[N];
 7 inline ll lowbit(ll k)
 8 {
 9     return k&(-k);
10 }
11 void update(ll c[],ll k,ll detal)
12 {
13     for(;k<N;k+=lowbit(k))
14         c[k]+=detal;
15 }
16 ll getsum(ll c[],ll k)
17 {
18     ll s=0;
19     for(;k>0;k-=lowbit(k))
20         s+=c[k];
21     return s;
22 }
23 int main(void)
24 {
25     ll n,m;
26     while(scanf("%I64d",&n)!=EOF)
27     {
28         memset(cnt,0,sizeof(cnt));
29         memset(ssum,0,sizeof(ssum));
30         memset(tsum,0,sizeof(tsum));
31         ll s=0,temp=0;
32         for(ll i=1;i<=n;i++){
33             scanf("%I64d",&m);
34             update(cnt,m,1); 
35             update(ssum,m,m);
36             update(tsum,i,m);
37             temp=getsum(cnt,m-1);
38             s+=m*(i-temp-1);
39             s+=getsum(tsum,i-1);
40             s-=getsum(ssum,m-1); 
41             //printf("**%I64d\n",s);
42         } 
43         printf("%I64d\n",s);
44     }
45     return 0;
46 }      

轉載于:https://www.cnblogs.com/GO-NO-1/p/3690889.html