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;
}