寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

Aizu Online Judge in C++ #ALDS1_5_D : The Number of Inversions

Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。

・問題 "The Number of Inversions"
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_5_D
数列 A={a0,a1,...an−1} について、ai>aj かつ i

Aizu Online Judge in C++ #ALDS1_5_D : The Number of Inversions
/*
Aizu Online Judge in C++ #ALDS1_5_D : The Number of Inversions
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_5_D
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000001
long long ans=0;
void merge(int a[],int left,int mid,int right){
    int nl=mid-left;
    int nr=right-mid;
    int l[nl+1],r[nr+1];
    for(int i=0;i<nl;i++){
        l[i]=a[left+i];
    }
    for(int i=0;i<nr;i++){
        r[i]=a[mid+i];
    }
    l[nl]=r[nr]=INF;
    int i=0;
    int j=0;
    for(int k=left;k<right;k++){
        if(l[i]<r[j]){
            a[k]=l[i];
            i++;
        }else{
            a[k]=r[j];
            j++;
            ans+=(nl-i);
        }
    }
}
void mergeSort(int a[],int left,int right){
    if(left+1<right){
        int mid=(left+right)/2;
        mergeSort(a,left,mid);
        mergeSort(a,mid,right);
        merge(a,left,mid,right);
    }
}
int main(void){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    mergeSort(a,0,n);
    cout<<ans<<endl;
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/