HDU - 2838 Cow Sorting （树状数组）

题意：求排列成升序的花费，每次只能交换相邻的两个数，且话费为两个数字的和，求最小的话费

思路：先设想一下，每个数字会被交换的可能，一个是当前面有大于它的数字，一个是当后面有小于它的数字两种情况，这样我们就可以联想到树状数组了，每次看看该数面有多少小于它的，就可以求出多少大于它的了，然后倒着求小于它的情况，起初一直挖，改着改着就A了，还有太大的数组一定要定义成全局变量

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
#define ll long long 

ll num[MAXN],b[MAXN],c[MAXN];
ll ans;
int n;

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

void add(ll a[],ll pos,ll val){
	while (pos <= MAXN){
		a[pos] += val;
		pos += lowbit(pos);
	}
}

ll sum(ll a[],ll pos){
	ll tmp = 0;
	while (pos > 0){
		tmp += a[pos];
		pos -= lowbit(pos);
	}
	return tmp;
}

int main(){
	while (cin >> n){
		memset(c,0,sizeof(c));
		memset(b,0,sizeof(b));
		memset(num,0,sizeof(num));
		ans = 0;
		for (int i = 1; i <= n; i++){
			cin >> num[i];
			add(c,num[i],1);
			ans += num[i] * (i-sum(c,num[i]));
		}
		for (int i = n; i >= 1; i--){
			ans += num[i] * (sum(b,num[i]-1));
			add(b,num[i],1);
		}
		cout << ans << endl;
	}
	return 0;
}

HDU - 2838 Cow Sorting （树状数组）,布布扣,bubuko.com

HDU - 2838 Cow Sorting （树状数组）

原文：http://blog.csdn.net/u011345136/article/details/22979083