基本算法--分治法（快排，归并）习题

参考基本算法-分治法（快排，归并）-CSDN博客???????模板进行练习，旨在加强两个模板运用。

1.求逆序对（归并排序）

题目来源：P1908 逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中?ai?>aj??且?i<j?的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

输入格式：

第一行，一个数?n，表示序列中有?n个数。

第二行?n?个数，表示给定的序列。序列中每个数字不超过?1e9。

输出格式

输出序列中逆序对的数目。

思路

板子题，参考基本算法-分治法（快排，归并）-CSDN博客?归并排序模板加以修改，以cnt作为逆序对的个数。

当q[i]>q[j]时，cnt+=mid-i+1;即可求出逆序对的个数。

注意：此题数据量比较大，要开long long ，用int 过不去。

完整代码

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+10;
long long q[N],tmp[N],cnt=0;

void merge_sort(long long q[],long long l ,long long r){
	if(l>=r) return;
	long long mid=l+r>>1;
	merge_sort(q,l,mid);
	merge_sort(q,mid+1,r);
	
	long long k=0,i=l,j=mid+1;
	while(i<=mid&&j<=r){
		if(q[i]<=q[j]) tmp[k++]=q[i++];

		else {
			tmp[k++]=q[j++];
			cnt+=mid-i+1;			
		}
	}
	while(i<=mid) tmp[k++]=q[i++];
	while(j<=r) tmp[k++]=q[j++];
	
	for(long long i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
}

int main(){
	long long n;
	cin>>n;
	for(long long i=0;i<n;i++) scanf("%lld",&q[i]);
	merge_sort(q,0,n-1);
	cout<<cnt<<endl;
	return 0;
}

2.求第 k 小的数（快速排序）

题目来源：P1923 【深基9.例4】求第 k 小的数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

输入?n（1≤n<50000001≤n<5000000?且?n?为奇数）个数字?ai?（1≤ai?<1e9），输出这些数字的第?k?小的数。最小的数是第?0?小。

请尽量不要使用?nth_element?来写本题，因为本题的重点在于练习分治算法。

思路

方法一：

用快速排序直接排出q[]的大小，输出即可。

完整代码

#include<bits/stdc++.h>
using namespace std;

const int N=5e6+10;
typedef long long ll;
ll q[N];

void quick_sort(ll q[],ll l,ll r){
	if(l>=r) return;
	
	ll i=l-1,j=r+1,x=q[l+r>>1];
	while(i<j){
		do i++;while(q[i]<x);
		do j--;while(q[j]>x);
		if(i<j) swap(q[i],q[j]);
	}
	quick_sort(q,l,j);
	quick_sort(q,j+1,r);
}

int main(){
	ll n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++) scanf("%lld",&q[i]);
	quick_sort(q,0,n-1);
	cout<<q[m]<<endl;
	return 0;
}

方法二：

用c++自带STL库函数sort()排除大小，输出即可。

完整代码

#include<bits/stdc++.h>
using namespace std;

const int N=5e6+10;
typedef long long ll;
ll q[N];


int main(){
	ll n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++) scanf("%lld",&q[i]);
	sort(q,q+n);
	cout<<q[m]<<endl;
	return 0;
}

感谢大家的观看！