光荣的梦想(逆序对&&归并排序)

光荣的梦想

**Prince对他在这片大陆上维护的秩序感到满意,于是决定启程离开艾泽拉斯。在他动身之前,Prince决定赋予King__Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代,平衡是个梦想。因为有很多奇异的物种拥有各种不稳定的能量,平衡瞬间即被打破。KB决定求助于你,帮助他完成这个梦想。_

**一串数列即表示一个世界的状态。

**平衡是指这串数列以升序排列,而从一串无序数列到有序数列需要通过交换数列中的元素来实现。KB的能量只能交换相邻两个数字。他想知道他最少需要交换几次就能使数列有序。

输入格式
第一行为数列中数的个数 N(n≤100000)。
第二行为 N 个数 a1~an (每个数小于100000),表示当前数列的状态。

输出格式
输出一个整数,表示最少需要交换几次能达到平衡状态。

输入
4
2 1 4 3

输出
2

 #include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<iomanip>
using namespace std;

long long ans=0;
int a[500005],r[500005],n;

inline void zql(int s,int mid,int t)
{
    int k=s;
    int i=s;
    int j=mid+1;
    while(i<=mid&&j<=t)
        if(a[i]>a[j])
        {
            r[k++]=a[j++];
            ans=ans+(mid+1-i);
        }
        else
            r[k++]=a[i++];

    while(i<=mid)
        r[k++]=a[i++];
    while(j<=t)
        r[k++]=a[j++];

    for(i=s;i<=t;i++)
        a[i]=r[i];
}

inline void gl(int s,int t)
{
    if(s<t)
    {
        int mid=(s+t)/2;
        gl(s,mid);
        gl(mid+1,t);
        zql(s,mid,t);
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    gl(1,n);
    cout<<ans<<endl;
    return 0;
}

其中的逆序对和归并排序基本思想和具体实现是什么?望大神详解。

2个回答

……代码如上……
我只是想问一下其中的逆序对和归并排序基本思想和具体实现是什么?

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐