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操作.