首页 > 代码库 > 还是火柴排队(补一下归并排序的锅)

还是火柴排队(补一下归并排序的锅)

原文章传送门

好吧,我们上次说这道题可以用归并排序做。。

但是我不会归并排序的锅(真是蒟蒻。。)

早晨爬起来赶紧学一发。。

貌似还挺简单的。。

233~

好吧,切入正题。

归并排序其实就是利用了分治的思想。

分治:将一个大问题分为2个小问题,之后解决所有的小问题,再合并答案。

比如我们举一个数列,对它进行归并排序。

a[10]={9,2,3,5,4,6,6,7,9,5}

归并的顺序是这样的

{9,2,3,5,4}{6,6,7,9,5};

{9,2,3}{5,4}{6,6,7}{9,5};

{9,2}{3}{5,4}{6,6}{7}{9,5}

分到这一步后,有2种方法:

第一是继续分,然后归并,第二是不分,然后判断一下2个数的大小关系,如{9 2}变为{2 9}然后归并。。(其实复杂度差不多,就是少几个常数。。)

合并过程:(接上表)

{2,9}{3}{4 5}{6 6}{7}{5 9}

{2,3,9}{4,5}{6,6,7}{5,9}

{2,3,4,5,9}{5,6,6,7,9}

{2,3,4,5,5,6,6,7,9,9}

恩,就是这样。

合并的代码实现就是将2块数组放2个指针。

逐一扫描,比较。

然后把结果重新放回原数组中

好吧,感觉讲的不是很清楚。

还是上代码吧。。

#include<iostream>
#include<cstdio>
#include<algorithm>
#define mod 99999997
using namespace std;
struct lisan{
    int opt,value;
}a[100001],b[100001];
int result[100001],c[100001],d[100001],ans,n;
bool cmp(lisan a,lisan b){ return a.value<b.value;}
void mergesort(int left,int right){
    if(left>=right)return ;
    int mid=(left+right)>>1,i,j,k;    
    mergesort(left,mid);
    mergesort(mid+1,right);
    for(i=left,j=mid+1,k=left;i<=mid&&j<=right;k++)
    {
        if(c[i]<c[j])d[k]=c[i++];
        else ans+=mid-i+1,ans%=mod,d[k]=c[j++];
    }
    while(i<=mid)
    d[k++]=c[i++];
    while(j<=right)
    d[k++]=c[j++];
    for(i=left;i<=right;i++)
    c[i]=d[i];
}
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;
    mergesort(1,n);
    printf("%d",ans);
}

比树状数组快诶。(树状数组背锅。。)

其实都是O(nlogn)只不过常数小了点。

恩,就是这样。

线段树算法和乱七八糟的算法还是去死吧。。(等我成为蒟蒻中的巨神再回来补。。)

还是火柴排队(补一下归并排序的锅)