本文共 608 字，大约阅读时间需要 2 分钟。

对于每一个位置的高度，如果想要交换次数最少，肯定要把在它后边比它小的换到前面，在它前面比它大的换到后边。然后我们发现其实这就是求整个序列的逆序对数，普通的暴力方法求逆序对肯定会超时，我们采用树状数组求逆序对。然后对于每个位置求得的结果带入等差数列求和公式求得结果。

代码如下：

#include
   
    using namespace std;int n;int c[100007],d[100007];long long ans[100007];struct node{
      int val;   int pos;}p[100007];int lowbit(int x){
       return x&(-x);}bool cmp(node x,node y){
       return x.val
    
     =1;i--)    {
           in(d[i]);        ans[i]+=getsum(d[i]-1);//求得应该在这个位置后边但是在这个位置前面的个数    }    long long sum=0;    for(int i=1;i<=n;i++)    {
           sum+=(ans[i]+1)*ans[i]/2;//等差数列求和公式求和    }    printf("%lld\n",sum);    return 0;}
    
   

转载地址：http://dsgwi.baihongyu.com/