今天来水一道题目, 名字叫逆序对.
主要是复习一下归并排序的写法.
Code
#include <bits/stdc++.h>
using namespace std;
#define MAXN 500005
#define F(i, a, b) for(int i=a; i<=b;i++)
#define Fd(i, a, b) for(int i=a;i>=b;i--)
int a[MAXN], c[MAXN], n;
long long ans;
void msort(int b, int e){
if(b==e) return;
int mid = (b+e)/2, i=b; int j=mid+1, k=b;
msort(b, mid); msort(mid+1, e);
while(i<=mid && j<=e){
if(a[i]<=a[j]) c[k++]=a[i++];
else{
c[k++]=a[j++];
ans += (mid-i+1);
}
}
while(i<=mid) c[k++] = a[i++];
while(j<=e) c[k++] = a[j++];
F(i, b, e) a[i] = c[i];
}
int main(){
int n; cin>>n;
F(i, 1, n) cin>>a[i];
msort(1,n);
cout<<ans<<endl;
}
标签:int,mid,long,msort,MAXN,逆序
From: https://www.cnblogs.com/augpath/p/16905350.html