本文主要是介绍HDU 2838 Cow Sorting，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接~~>
做题感悟：开始做时感觉很难，顿时有种百度的想法不过还是坚持了下来.
解题思路：和求逆序数差不多这题是求和。可以开两个数组一个用于记录比当前数小的个数，以记录已经出现的比当前数小的和。这样 best = sum (出现的所有数的和) - 比它小的数的和 + （ 前面所有数的个数 - 比当前数小的个数 ） * 当前数的值 . sum - 比它小的数的和 即：前面比它大的数的和 （ 前面所有数的个数 - 比当前数小的个数 ） * 当前数的值 即 ：逆序数的个数 * 当前值 .（PS：需用__int64 ）
代码：
#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
#define LEN sizeof(struct node)
#define lld __int64
const double PI = 3.1415926535898 ;
const int INF = 99999999 ;
const double esp = 1e-8 ;
const double g = 9.8 ;
const long long mod= 1000 ;
const int MX = 100005 ;
lld n ;
lld c[MX],num[MX] ; // c[] 记录比它小的数的和 num[] 记录个数
lld lowbit(lld x)
{return x & (-x) ;
}
void add(lld x,lld nx)// 在父亲那更新个数和比它小的和
{while(x<=n){num[x]++ ;c[x]+=nx ;x+=lowbit(x) ;}
}
lld su(lld x) // 计算比它小的个数
{lld ans=0 ;while(x>0){ans+=num[x] ;x-=lowbit(x) ;}return ans ;
}
lld get_su(lld x) // 求比它小的数所有的和
{lld ans=0 ;while(x>0){ans+=c[x] ;x-=lowbit(x) ;}return ans ;
}
int main()
{lld x ;while(~scanf("%I64d",&n)){memset(c,0,sizeof(c)) ;memset(num,0,sizeof(num)) ;lld summ=0,best=0,sum=0,num1 ;for(int i=1 ;i<=n ;i++){scanf("%I64d",&x) ;num1=su(x) ; //比它小的个数sum=get_su(x) ; // 比它小的和best+=summ-sum+(i-1-num1)*x ;add(x,x) ;// 更新个数summ+=x ;}printf("%I64d\n",best) ;}return 0 ;
}
这篇关于HDU 2838 Cow Sorting的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
