/***************************************************************************************************************** 题意：给你N个排列不规则的数，任务是把它从小到大排好，每次只能交换相邻两个数，交换一次的代价为两数之和，求最小代价注意 每次交换 都必须只能交换相邻的2个 思路：对于当前数X，我们如果知道前面比它大的数有多少，假设为K，那么有部分代价是确定的，那就是K*X；然后还得加上比它大的那些数之和，这就是当数列到X为止，排好所需要的最小代价。**********************************************************************************************************************/#include<iostream>#include<cstring>using namespace std;const int maxn=100001; struct node{ int cnt; __int64 sum;}tree[maxn]; int n;int lowBit(int x){ return x&(-x);}void modify(int x,int y,int t){ while(x<=n) { tree[x].sum+=y; tree[x].cnt+=t; //tree[].cnt来保存是否出现过a x+=lowBit(x); }}__int64 query_cnt(int x) //比x小的数的个数 { __int64 sum=0; while(x>0) { sum+=tree[x].cnt; x-=lowBit(x); } return sum;}__int64 query_sum(int x) //比x小的所有数之和 { __int64 sum=0; while(x>0) { sum+=tree[x].sum; x-=lowBit(x); } return sum;}int main(){ while(~scanf("%d",&n)) { int a; __int64 ans=0; memset(tree,0,sizeof(tree)); for(int i=1;i<=n;i++) { scanf("%d",&a); modify(a,a,1); //以a为下标更新数组 __int64 k1=i-query_cnt(a); //k1为前i个数比a大的数的个数 if(k1!=0) { __int64 k2=query_sum(n)-query_sum(a); //目前所有数的和-目前所有比a小的数的和，为比a大的数的和 ans+=k1*a+k2; //调换a所需的时间 } } printf("%I64d
",ans); } system("pause"); return 0;}