首页 > 代码库 > 火柴排队(NOIP2013)(附树状数组专题讲解(其实只是粗略。。。))

火柴排队(NOIP2013)(附树状数组专题讲解(其实只是粗略。。。))

原题传送门。。(9018上不去。明天再来搞。)

首先,这道题目是一道神奇的题。

看到这道题,第一眼就觉得2个数组排个序,然后一一对应的时候一定差值最小。

由于我们可以将这2个数列同时进行调换。

所以我们先把2个数列排个序。

第二个序列中的数组的下标都指向第一个数组中的数的原来位置(其实就是离散化(真是啰嗦。。))

离散化之后,我们就变成了一个混乱的数列变成升序数列的操作次数是多少。

然后自然就会想到逆序对。每次变换之后逆序对的个数最多只能-1;

所以答案就是数列中逆序对的个数。

然后就是求逆序对啦。

逆序对有很多种做法:

TOP1:暴力O(N^2)时间TLE BOOM。。。!

TOP2:归并排序

TOP3:线段树

TOP4:树状数组(就是我写的)(又短又好写233~(PS:其实是其他的不会。。))

好吧。

其实我树状数组写的时候也不会,现学的。。

顺便讲讲树状数组的几个基本操作;

NUM1: update

代码如下:

void update(int x)
{
    while(x<=n)
    {
        d[x]++;
        x+=lowbit(x);    
    }    
}

这就相当于给树状数组赋值/(+/-一个值)

在此lowbit就是x在二进制下的第一个1的位置。

实在看不懂可以找规律: 比如x=1时,n=8时,我们要赋值的数组为d[1],d[2],d[4],d[8];

当x=3时,我们要赋值的数组为d[3],d[4],d[8];

x=5:d[5],d[6],d[8];

恩,就是这样。

NUM2:getsum(相当于查询)

下面贴代码

int getsum(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=d[x];
        x-=lowbit(x);    
    }
    return ans;
}

相当于上一个查询顺序反过来(好像语序有问题。。。)

然后呢,这题就用这2个函数来求逆序对的个数。

在本代码中getsum(x)求的是x之前<=x的数的数量。

这样i-getsum(x)就是x之前>x的数的数量

即对于x的逆序对个数

最后累加一下,就是答案啦!

注意!在本代码中,c数组用于离散化,防止爆栈,同时也加快效率。

d[i]表示在c[i-lowbit(i)]到c[i]中<=c[i]的数出现的总次数!(重点!这个点我理解了很久,要多多消化。也许是因为我蒟蒻。。。)

好吧,下面贴代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int c[100001];
struct lisan{
    int value,opt;
}a[100001],b[100001];
int cmp(lisan a,lisan b){return a.value<b.value;}
int d[100001];
int n;
int lowbit(int x){return x&(-x);}
void update(int x)
{
    while(x<=n)
    {
        d[x]++;
        x+=lowbit(x);    
    }    
}
int getsum(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=d[x];
        x-=lowbit(x);    
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&a[i].value);
    a[i].opt=i;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&b[i].value);
        b[i].opt=i;
    }
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++)
    c[b[i].opt]=a[i].opt;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        update(c[i]);
        ans+=i-getsum(c[i]);
        ans=ans%99999997;
    }
    printf("%d\n",ans);
}

祝大家编程愉快啦233~(反正我理解了1个多小时。。)

然后狠狠的被CLZ,QRC等一群学弟和zxyerD了一顿。。

火柴排队(NOIP2013)(附树状数组专题讲解(其实只是粗略。。。))