HDU2838 Cow Sorting (樹狀數組)

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=2838

題意如下：有n個數，從1-n，把這n個按照遞增的順序排列，每次隻能夠交換相鄰的兩個數，交換的代價為兩數字之和，求交換的最小代價。

思路：如果第i個數要交換要具備以下兩個條件之一：第i個數前面有大于它的數或者第i個後面有小于它的數。是以題目就可以轉化為：求第i個數字前面有幾個大于它的數和後面有幾個小于它的數，用樹狀數組來維護數組，時間複雜度（nlgn）；

AC代碼如下：

實作方法一：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;

const int maxn = 1e5 + 5;
ll tree[maxn],a[maxn];
int n;

int lowbit(int k){
	return k & -k;
}

void update(int k, int num){
    while(k < maxn){
        tree[k] += num;
        k += lowbit(k);
    }
}

int query(int k){
    int sum = 0;
    while(k){
        sum += tree[k];
        k -= lowbit(k);
    }
    return sum;
}

int main(){
    while(~scanf("%d",&n)){
        for(int i = 1; i <= n; i ++){
            scanf("%lld",&a[i]);
        }
        memset(tree,0,sizeof(tree));
        ll ans = 0;
        for(int i = 1; i <= n; i ++){
        	ll num = query(a[i]);
            ans += (i - 1 - num) * a[i];
            update(a[i],1); 
        }
        memset(tree,0,sizeof(tree));
        for(int i = n; i > 0; i --){
        	ll num = query(a[i]);
            ans += num * a[i];
            update(a[i],1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}
           

實作方法二：求出前面小于它的數num，則 a[i] - 1- num就是後面小于它的數的個數。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;

const int maxn = 1e5 + 5;
ll tree[maxn],a[maxn];
int n;

int lowbit(int k){
	return k & -k;
}

void update(int k, int num){
    while(k < maxn){
        tree[k] += num;
        k += lowbit(k);
    }
}

int query(int k){
    int sum = 0;
    while(k){
        sum += tree[k];
        k -= lowbit(k);
    }
    return sum;
}

int main(){
    while(~scanf("%d",&n)){
        for(int i = 1; i <= n; i ++){
            scanf("%lld",&a[i]);
        }
        memset(tree,0,sizeof(tree));
        ll ans = 0;
        for(int i = 1; i <= n; i ++){
        	ll num = query(a[i]);
            ans += (i - 1 - num) * a[i];
            ans += (a[i] - 1 - num) * a[i]; 
            update(a[i],1); 
        }
        printf("%lld\n",ans);
    }
    return 0;
}