技术教程 编程教程 poj2299(归并排序求逆序对) 正文

poj2299(归并排序求逆序对)

2023-04-23,,

题目链接：https://vjudge.net/problem/POJ-2299

题意：给定一个序列，每次只能交换邻近的两个元素，问要交换多少次才能使序列按升序排列。

思路：本质就是求逆序对。我们用归并排序求逆序对，这也是简单的cdq分治。

#include<cstdio>

#include<algorithm>

#include<cstdlib>

#include<cmath>

using namespace std;

typedef long long LL;

const int maxn=5e5+;

int n,a[maxn],tmp[maxn];

LL ans;

void merge_sort(int l,int r){

    if(l==r) return;

    int mid=(l+r)>>;

    int t1=l,t2=mid+,cnt=l;

    merge_sort(l,mid);

    merge_sort(mid+,r);

    while(t1<=mid||t2<=r){

        if(t2>r||(t1<=mid&&a[t1]<=a[t2]))

            tmp[cnt++]=a[t1++];

        else{

            ans+=(mid-t1+);

            tmp[cnt++]=a[t2++];

        }

    }

    for(int i=l;i<=r;++i)

        a[i]=tmp[i];

}

int main(){

    while(scanf("%d",&n),n){

        ans=;

        for(int i=;i<=n;++i)

            scanf("%d",&a[i]);

        merge_sort(,n);

        printf("%lld\n",ans);

    }

    return ;

}

poj2299(归并排序求逆序对)的相关教程结束。

《poj2299(归并排序求逆序对).doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!