HDU2838 Cow Sorting（树状数组求逆序对的变式）

HDU2838 Cow Sorting

题目大意

一组数需要从小到大排序，排序操作是仅能交换相邻的两数，代价是这两个数的代数和，计算最小的代价.

题目解析

看到相邻的两数，心里咯噔一下：又是逆序对！

但是这道题不太一样，除了求最小交换次数，还要求交换的代价.

我们不妨举个栗子：

3 4 2 1
           

对于这组数据而言，无论是2还是1，都需要与原数组中左边比它大的3和4进行交换，也就是说，对于每个数，我们都可以在把它加入原数组的时候预处理其左边比它大的数的个数以及这些数的大小.

而我们知道，树状数组求逆序对时是按照大到小先后加入原数组的，这就很方便预处理了.

再来看一看代数和可以怎么简化地表示.

∑ ( a i + n o w ) = n o w ∗ s u m + ∑ a i \sum (a_i+now)=now*sum+\sum a_i ∑(ai​+now)=now∗sum+∑ai​

这个式子的意义如下：

总的代数和=所有在原数组中在它左边且比它大的数的和+现在这个新加入原数组的数*前述数的个数.

程序实现

#include<bits/stdc++.h>
#define ll long long//记得开long long
#define maxn 100010
using namespace std;
struct number{
	ll key,rank;
}a[maxn];
int n;
ll tree[maxn],tree_sum[maxn],ans;
bool cmp(number x,number y){
	return x.key >y.key ;
}
int lowbit(int x){return x&(-x);}
void add(ll x,ll k){
	for(int i=x;i<=n;i+=lowbit(i)){tree[i]+=k;tree_sum[i]+=1;}//tree为记录原数组的树状数组，tree_sum为记录前缀和数的数组
}
ll query(ll x){
	ll ret=0;
	for(int i=x;i;i-=lowbit(i))ret+=tree[i];
	return ret;
}
ll query_sum(ll x){
	ll ret=0;
	for(int i=x;i;i-=lowbit(i))ret+=tree_sum[i];
	return ret;
}
int main(){
	while(~scanf("%d",&n)){//看好这个用法
		memset(tree,0,sizeof tree);
		memset(tree_sum,0,sizeof tree_sum);
		memset(a,0,sizeof a);
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i].key );
			a[i].rank =i;
		}
		sort(a+1,a+n+1,cmp);//倒序求逆序对
		for(int i=1;i<=n;i++){
			add(a[i].rank ,a[i].key );//把数据添加回原数组的原位置
			ans+=(a[i].key *query_sum(a[i].rank -1)+query(a[i].rank -1));//如上述的简化表示
			//printf("%lld\n",query(a[i].rank -1));
		}
		printf("%lld\n",ans);
	}
	return 0;
}
           

对树状数组求逆序对的思想更加熟悉掌握了，尤其是add操作.