历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1215. 小朋友排队原题链接中等

作者：

就是氧气 , 2019-12-30 19:52:21 , 所有人可见 , 阅读 10935

144

39

首发题解来了~

思路：

算法1暴力，算法2树状数组

先看暴力，树状数组解释在算法2中

这个题实际上是逆序对，只不过稍稍变形，我们来看对于每个数来说他的逆序对怎么算，在这个数之前比这个数大数+这个数之后比这个数小的数就是这个数的逆序对的个数（好绕口。。。慢慢体会）。这个逆序对个数其实代表了该数换位置的次数。
为什么？
带入算组数据就可以了，算出来次数之后通过等差数列来计算出这帮小盆友的不高兴程度就可以了，最后把每个小盆友不高兴和相加就是答案。

问题在于怎么算逆序对个数，这个题和归并排序有一定差别，当然也是可以用归并去做的，但我确实没想出来，卡在了如何求每个小盆友的换位次数（也就是逆序对的数量）,最简单的思路就是双重for循环暴力去求，很可惜，被卡了，因为n是100000，能过5个数据，代码如下

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
long long ans;
long long a[N],num[N];

long long summary(long long x){
    int k;
    k=(1+x)*x/2;
    return k;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    for(int i=1;i<=n;i++){
        long long res=0;
        for(int j=1;j<i;j++){
            if(a[j]>a[i]){
                res++;
            }
        }

        for(int j=i+1;j<=n;j++){
            if(a[j]<a[i]){
                res++;
            }
        }

        res=summary(res);
        num[i]=res;
    }

    for(int i=1;i<=n;i++){
        ans+=num[i];
    }

    cout<<ans<<endl;
    return 0;
}

算法2 树状数组

如果用树状数组去维护就没有问题了，思路也是卡了我2小时。。。。
每个数所对应的换位次数（逆序对）=前面比它大的+后面比它小的咳咳，貌似又废话了一遍~~~
每次读入一个数就先把它放到树状数组中去，但这个树状数组保存的并不是这个数，而是这个数出现的次数。。
只要明白了这个道理就很简单了，放入完毕后，我们就去query一下这个数之前有多少个比他小的数，然后用当前数组长度减去比这个数小的数就是比这个数大的数的个数了（算比这个数大的个数）。
比当前数靠后的且别当数小的数求法就是把这个树状数组给倒过来求一遍。

说了一堆这么绕口的话，我举个例子吧，语文不好各位理解一下hhhhh
我们看这组数据
5 2 3 4 1
当我们判断到第四个数也就是4的时候，我们树状数组维护了那些信息，仔细看我上面加粗的字体，在4之前5出现了1次，2出现了一次，3出现了1次此时，树状数组(把0空过去,数据都不考虑0，即使出现0我们让每个数都++，这样不影响结果也不出现0)tr[1]=0，tr[2]=1,tr[3]=1,tr[4]=1,tr[5]=1,而在4之前比4大的数只有5，怎么算，在这里我们并不知道比4大的数就是5，也可能是另一个数，但我们只需要知道比4大的个数就行了，那我们用当前的个数减去比4小的个数不就好了，对啊，所以说比他大的数4-query（4）=1，比4小的个数求法，我们倒着看，怎么看着简单呢？，你把数组倒过来，看成1，4，3，2，5，比他小的就是query（4）=2（注意，在这里，两个数组是一样的，所以其维护的树状数组里的值也是不同，所以query（4）不同！！！，query就是计算比当前数（例子中是4）小的个数之和），所以4这个小盆友他的换位次数2+1=3，咦，不对啊，可4逆序数对是2怎和结论冲突了呢，就是这个破bug，害得我又找了半个小时，实际上query这个操作把自己也算进去了，而4只能被算一次，所以求比4小的数应该算成query（3）而不是query（4），因为4已经在上面算过了，这点不太懂得去看下树状数组中的区间和[x-lowbit(x),x]是闭区间，所以说把x算进去了，这个地方注意下就可以了，行了不废话了，代码走起。

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n;
long long a[N],tr[N],b[N]={0};

int lowbit(int x){
    return x&-x;
}

void add(int x,int y){
    for(int i=x;i<N;i+=lowbit(i)) tr[i]+=y;
}

int query(int x){
    int ans=0;
    for(int i=x;i;i-=lowbit(i)) ans+=tr[i];
    return ans;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]++; //避免0
    }

    for(int i=1;i<=n;i++){
        add(a[i],1);
        b[i]=(i)-query(a[i]); //比这个数大的个数
    }
    // cout<<endl;

    memset(tr,0,sizeof tr); //该逆序算了，所以维护树状数组不一样，所以算完大的要清0.

    for(int i=n;i>=1;i--){
        add(a[i],1);
        b[i]+=query(a[i]-1);  //比这个数小
    }

    long long res=0;

    // for(int i=1;i<=n;i++){
    //     cout<<b[i]<<endl;
    // }
    for(int i=1;i<=n;i++){
        res+=(1+b[i])*b[i]/2;
    }

    cout<<res<<endl;
    return 0;
}

题解不易，如果有帮助，留下小心心哦~~~~

39 评论

lightmon5210 2023-02-06 22:08

为什么b[i] = i - query(a[i]), 为什么是用i减去啊

Q.Q 2023-02-07 17:34

我想了一下，他这里是先把a[i]加到树状数组里了，所以此时此刻要统计比a[i]大的数的个数的话就是：放进去的数的总数-比a[i]小的数-数值等于自己的个数；由于树状数组query(x)时会默认把下标为x的元素也算上，所以实际上query返回的应该是此时此刻小于等于a[x]的个数，用i一减就是答案了

乾在云楼 2023-03-25 15:07

i是当前数字的个数，query查的是前面比ai小的数的个数，i-query就是前面比ai大的数的个数

命不该绝 2023-03-27 06:54

问一下为啥query(a[i] - 1) 的 a[i] 要减一

for(int i=n;i>=1;i--){
        add(a[i],1);
        b[i]+=query(a[i]-1);  //比这个数小
    }

唐康辉 2023-03-27 19:40

我们是逆序算后面多少比这个数小，所以是a[i]-1

命不该绝 2023-04-07 20:13 回复了唐康辉的评论

a[i] - 1是查找的多少个小于等于这个数吧

Happy_hacking 9个月前

不能算自身

水羊 2023-02-21 16:33

我感觉b[i]=(i)-query(a[i])就是为了得到树状数组中在i前面，且比i大的数而b[i]+=query(a[i]-1);，提前把数组倒序，这样就可以按照正常顺序求出在没倒序之前树状数组中在i后面且比i小的数的多少。

MoniFeng 2023-02-08 09:54

Orz

baikun 8个月前

每个数所对应的换位次数（逆序对）=前面比它大的+后面比它小的
为什么？？？

哇怎么什么都不会 9个月前

关于逆序对：有人说在这个数之前比这个数大的数的个数,（确实有些题是这样说的）
本文说：在这个数之前比这个数大数+这个数之后比这个数小的数就是这个数的逆序对的个数，
我想问下这个该怎么区分

沉华 8个月前

其实就是当 i < j 时，a[ i ] > a[ j ]；当 i > j 时， a[ i ] < a[ j ]，这就是逆序对

ZZZHHHXXX 9个月前

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
ll a[N],n,d[N],tr[N],max_n;
ll lowbit(ll val){
    return val&-val;
}
void add(ll x,ll val){
    for(ll i=x;i<=max_n;i+=lowbit(i)){
        tr[i]+=val;
    }
}
ll sum(ll x){
    ll res=0;
    for(ll i=x;i;i-=lowbit(i)){
        res+=tr[i];
    }
    return res;
}
ll get_res(ll val){
    return val%2?(val+1)/2*val:val/2*(val+1);
}
int main()
{
    //树状数组：插入/修改——o(nlogn),求前缀和——o(nlogn);
    //思路：查找每个数的逆序对个数——用等差求和公式求出每个数的前n项和
    //逆序对：此数之前比此数大的数，此数之后比此数小的数
    //解题思想：求大值：将每个数的出现次数数插入树状数组，遍历此数目前<=它的数的个数，用此时总数减去这个个数即为出现的大数个数
              //求小值：将每个数反过来插入树状数组即可（注意要求比它-1<=的前缀和个数）。
    cin>>n;
    ll res=0;
    for(ll i=1;i<=n;i++){
        scanf("%d",a+i);
        a[i]++;//防止0的出现
        max_n=max(max_n,a[i]); //最大遍历的界限
    }
    for(ll i=1;i<=n;i++){
        add(a[i],1);//统计目前出现的数的数量
        d[i]=i-sum(a[i]);//获得之前大于此数的数的个数
    }
    memset(tr,0,sizeof tr);
    for(ll i=n;i;i--){
        add(a[i],1);
        d[i]+=sum(a[i]-1);//不包含此数，获得之后小于此数的个数
        res+=get_res(d[i]);//求解每个数逆序对的心情值
    }
    cout<<res;
    return 0;
}

dflying 9个月前

树状数组的写法妙啊

geeker_bin 2023-03-08 17:08

Orz

等等__ 2022-04-05 18:18

tr数组维护的应该是部分个数和，例子中tr数组应该有的不是1

星光下的舞蹈 2022-03-13 11:29

为什么最后要等差一下啊大佬

SapphireMoonlight 2022-03-18 17:31

假设某个位置上的数被交换次数为k，则这个数的不满意度为k + k-1 + k-2 + … + 1，即等差数列求和

acw大将军 2022-03-06 15:42

看不懂，这个等差数列是怎么推导出来的

lcx812 2022-03-20 18:04

1+2+3+…+n->(1+n+2+(n-1)+....+n+1)/2（n个数，每个数大小为n+1，相当于2所以要/2）->(n(n+1))/2

猪头肉 2020-07-24 14:30

老哥我想问一下，add函数中为啥i从x到N,而不是到n

就是氧气 2020-07-25 08:35

树状数组维护的是部分和所以一旦有数字更新就需要将树状数组全部更新一遍

猪头肉 2020-07-25 13:29 回复了就是氧气的评论

好的，谢谢大佬

就是氧气 2020-07-26 09:39 回复了猪头肉的评论

比如a[1]需要更新那么所有与a[1]相关的部分和都要更新对吧这就是树状数组hhhh 我是萌新

K_P 2022-03-21 20:07

树状数组维护的是高度而高度的范围是到N所以是N

ppplh 2023-01-29 22:10 回复了 K_P 的评论

哇我就是错在这里了，把人数和高度搞混了，改了几个小时，后来同学引以为戒

哈哈哈hh 2020-07-06 17:13

大佬们这里计算比它大的时候为什么要先add(),为什么不能改变顺序啊

    for(int i=1;i<=n;i++){
        add(a[i],1);
        b[i]=(i)-query(a[i]); //比这个数大的个数
    }

就是氧气 2020-07-07 08:29

仔细看一下 query（）操作中a[i]被上面的add（）所影响了为什么是因为有一个循环是需要考虑大于等于自己的

哈哈哈hh 2020-07-07 13:14 回复了就是氧气的评论

老哥还有一个问题，为什么我这样写就对了，

    for(int i = 1; i <= n; i ++) scanf("%d", &h[i]), h[i] ++, max_ = max(max_,h[i]);

    //求每个数前面有多少个数比他大
    for(int i = 1; i <= n; i ++){
         add(h[i], 1);
         sum[i] = query(max_) - query(h[i]);

    }

但是我要将max_ 改为 N 1000010; 就错了，这里的max_是最大值，那么N不是也可以吗