本文主要是介绍http://acm.hdu.edu.cn/showproblem.php?pid=2838逆序数的应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这算是一道比较综合的树状数组题。。
题意：一个农场主养了很多奶牛，每天晚上该农场主都要为奶牛，但是每个奶牛都有一个脾气，这可能会导致奶牛损坏农场主喂牛的工具。。每个奶牛的脾气不等，这样农场主可以调换的某两个牛的位置，以求奶牛破坏最少的工具。已知挪动两个奶牛花费的时间为两个奶牛脾气的和。。让你求出最少的时间在破坏最少工具的前提下。。
思路：树状数组中有两个元素一个是记录比当前a小的个数，一个是记录比当前a小的数的和。。mintime=a*(i-Quary_cnt(a))+Quary_sum(n)-Quary_sum(a);
#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#define M 100001
using namespace std;
typedef long long L;
int n;
typedef struct str
{ int cnt;L sum;
}Node;
Node s[M];
inline int lowbit(int x)
{return x&(-x);}
void update(int x,int y)
{ while(x<=n){ s[x].sum+=y;s[x].cnt++;x+=lowbit(x);}
}
L Quary_sum(int x)
{ L res=0;while(x>0){ res+=s[x].sum;x-=lowbit(x);}return res;
}
L Quary_cnt(int x)
{ L res=0;while(x>0){ res+=s[x].cnt;x-=lowbit(x);}return res;
}
int main()
{ while(~scanf("%d",&n)){ memset(s,0,sizeof(s));int a;L s1=0;for(int i=1;i<=n;++i){ scanf("%d",&a);update(a,a);L res=i-Quary_cnt(a);//求逆序数的个数if(res!=0){ L k=Quary_sum(n)-Quary_sum(a);//比a大的所有元素的和s1+=(k+res*a);}}printf("%I64d\n",s1);}return 0;
}这篇关于http://acm.hdu.edu.cn/showproblem.php?pid=2838逆序数的应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
