WUST 1954 小朋友排队（树状数组+求两次逆序对）

末蓝、 2022-06-11 07:16 178阅读 0赞

## 1954: 小朋友排队 ##

Time Limit: 1 Sec Memory Limit: 256 MB 64bit IO Format: %lld  
Submitted: 2 Accepted: 2  
\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

## Description ##

n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。

每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。

如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。

请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。

如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。

## Input ##

输入的第一行包含一个整数n，表示小朋友的个数。

第二行包含 n 个整数 H1 H2 … Hn，分别表示每个小朋友的身高。

1<=n<=100000，0<=Hi<=1000000

## Output ##

输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。

## Sample Input ![copy.gif][]      ##

3
    3 2 1

## Sample Output ##

\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

题解：

这是WUSTOJ上挂的2014年蓝桥杯本科B组预选赛的一题， 看着就是求逆序对，一开始没啥思路，后来想通了每个小朋友最后累加的愤怒值就是看他之前有多少个比他大的数加上之后有多少和比他小的数就做出来了，设该值为x的话，那么该小朋友累加的愤怒值就是x\*（x+1）/2;因为1+2+3...+x嘛，因为这里是要求单点的逆序对数，归并排序不知道怎么求单点的，正好之前用树状数组和线段树写过求逆序对数的题，就用上了，然后这题因为数据1e7，开线段树不离散化的话会炸内存，但是树状数组就不会了，而且还省去了离散化，这题总体思路就是正着求一遍逆序对，反着求一遍逆序对

ps：

如果还不会树状数组，可以看之前的博客，比较基础的例题和讲解：[点击打开链接][Link 1]

再上一题基础例题讲解：[点击打开链接][Link 2]

然后学会树状数组后树状数组和线段树求逆序对思路都是一样的：

按照输入的数列一个个插入到树中，设插入的数为x，该数是插入的第i个数的话（从0开始），插入前求一下树上小于等于x的已经插入数的个数，求得就是单点的逆序对数为：i减去该数（原理就是插入数-正序对数等于逆序对数）

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    int sum1[1000005];//用于正着求一遍逆序对的树状数组
    int sum2[1000005];//反着求的树状数组
    int p[1000005];//存数据
    int b[1000005];//存第一遍的每个点的逆序对数
    int lowbit(int x)
    {
        return x&(-x);
    }
    void update(int x,int a[])//线段树的单点更新
    {
         while(x<=1000001)//为什么填1000001和下面的操作有关
        {
            a[x]++;
            x+=lowbit(x);
        }
    }
    int query(int x,int a[])//询问
    {
        int s=0;
        while(x>0)//因为这里如果x等于零的时候lowbit也为0，会无限循环，所以下面处理数据的时候全部加1，所以界限为1000001
        {
            s+=a[x];
            x-=lowbit(x);
        }
        return s;
    }
    int main()
    {
        int i,j,k,n,t;
        long long s;
        while(scanf("%d",&n)!=EOF)
        {
            s=0;
            memset(sum1,0,sizeof(sum1));
            memset(sum2,0,sizeof(sum2));
            for(i=0;i<n;i++)
            {
                scanf("%d",&p[i]);
                p[i]+=1;//这里全部加上1防无限循环
                b[i]=i-query(p[i],sum1);//插入数-正序对数为逆序对数
                update(p[i],sum1);//更新
            }
            for(i=n-1;i>=0;i--)//反着再求一遍
            {
                t=query(1000001-p[i],sum2);
                s=s+((b[i]+t)*(1+b[i]+t)/2);//上面有推的公式
                update(p[i],sum2);
            }
            printf("%lld\n",s);
        }
        return 0;
    }

[Submit]: http://acm.wust.edu.cn/submitpage.php?id=1954&soj=0
[Status]: http://acm.wust.edu.cn/problemstatus.php?id=1954&soj=0
[Web Board]: http://acm.wust.edu.cn/bbs.php?pid=1954&soj=0
[copy.gif]: http://acm.wust.edu.cn/image/copy.gif
[Link 1]: http://blog.csdn.net/qq_37497322/article/details/74935461
[Link 2]: http://blog.csdn.net/qq_37497322/article/details/75007409