利用归并和快排的思想
分别可以快速求解逆序对和第 \(k\) 大 (小 )数
时间复杂度分别为\(O(nlogn)\)和\(O(n)\)
\(MergeSort\):
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N],b[N],ans;
void mergesort(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
mergesort(l,mid);
mergesort(mid+1,r);
int i=l,j=mid+1;
for(int k=l;k<=r;k++)
if(j>r||i<=mid&&a[i]<=a[j])
b[k]=a[i++];
else b[k]=a[j++],ans+=mid-i+1;
for(int k=l;k<=r;k++)a[k]=b[k];
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
mergesort(1,n);
printf("%d",ans);
return 0;
}
\(QuickSort\):
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int t[N],a[N],n,k,ans;
void quicksort(int l,int r){ //第k小数
if(l==r&&l==k){ans=a[k];return;}
if(l>r)return;
int i=l,j=r,res=a[l];
while(i<j){
while(i<j&&a[j]>res)j--;
if(i<j)swap(a[i],a[j]);
while(i<j&&a[i]<=res)i++;
if(i<j)swap(a[i],a[j]);
}
a[i]=res;
if(i==k){ans=a[k];return;}
else if(i>k)quicksort(l,i-1);
else quicksort(i+1,r);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
quicksort(1,n);
printf("%d",ans);
return 0;
}