少年Q

用户名：yin19990129

访问量：25365

签　名：

这次一定不水了！

等　　级
排　　名	181
经　　验	6821
参赛次数	2
文章发表	71
年　　龄	21
在职情况	学生
学　　校	宿迁学院
专　　业	软件工程

　　自我简介：

TA的其他文章

[STL训练]百步穿杨-题解(C++代码)只做最好的思路！
浏览：355

[STL训练]Ignatius and the Princess IV （C++代码）只做最好的思路！
浏览：176

[STL训练]Let the Balloon Rise-题解(C++代码)只做最好的思路！
浏览：269

你可能喜欢

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

16.求逆序对个数-题解(C++代码)只做最好的思路！

　　作者: 少年Q　　　　发表时间：2020-03-07 19:28:50 浏览：1845　|　评论：0　

原题链接：求逆序对个数

这题呢老师傅并没有给出答案，他让我们套用归并排序的算法来自行解决，但我尝试了很多遍都没有成功，心里很苦闷，于是就尝试了暴力枚举的方法来做这题，虽然结果是对的，但是没有通过，时间超限了33%，代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[100005],sum=0;

int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			if(a[i]>a[j]){
				sum++;
			}
		}
	}
	cout<<sum;
	return 0;
}
```
于是我又尝试用归并排序来解决这题，又是无解。。。后来在网上搜到了一个完美的答案，他写的的归并排序不仅简洁易懂，而且让人眼前一亮，，，嗯。。。以后就套用他的模板了，O(∩_∩)O哈哈~代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
int a[N],b[N];//b为辅助数组
int cnt=0;
void merge_sort(int l,int r){
	if(r>l){//如果整个区间中元素个数大于1，则继续分割
	    int mid=(r+l)/2;
		int i=l; //辅助数组的下标
		int p=l,q=mid+1;
		merge_sort(l,mid);
		merge_sort(mid+1,r);
		//printf("%d-%d  %d-%d\n",p,mid ,q ,r);
		while(p<=mid||q<=r){//左右两部分只要有一部分不为空
			if(q>r||(p<=mid&&a[p]<=a[q])){//从左半数组复制到辅助数组
				b[i++]=a[p++];
			}else{
				b[i++]=a[q++];
				cnt+=mid-p+1;//将逆序对的个数累加起来
			}
		}
		for(i=l;i<=r;i++){
			a[i]=b[i];//将b中排好序的元素复制到a中
		}
	
	}      
}
int main(){
	int n;
	while(cin>>n){
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    }
    merge_sort(1,n);
    for(int i=1;i<=n;i++){
    	cout<<a[i]<<" ";
    }
    cout<<"逆序对有："<<cnt<<endl; 
    }
    return 0;
}
```
这个代码写的太完美了，自愧不如，向大神致敬！归并排序是利用递归来分组排序的，所以复杂度比较高，一般我们不用，但面对一些特征性问题（逆序对问题，合并子序列问题等等）时，归并排序依然是个不错的选择（至少归并排序比暴力枚举的时间复杂度要低很多）。这种描述归并排序的代码虽然接近完美，但如果用它来解决合并区间或者合并子序列的时候，也不是最好的选择，因为他没有将两个区间分开存储，倒是老师傅的方法更好些，这两种方法不如看成两种思维，具体问题要灵活运用。

0.0分

60 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

少年Q

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

一个简单易懂的代码

格式错误一万年，，有没有过了的来看看（终于过了）

点我有惊喜！你懂得！

16.求逆序对个数-题解(C++代码)只做最好的思路！

评论区

精彩推荐

简单的a+b （C语言代码）

淘淘的名单（C语言代码）答案错误？？？

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

众数问题（C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

交换Easy （C语言代码）

矩阵的对角线之和（C语言代码）

1197求助

少年Q

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

一个简单易懂的代码

格式错误一万年，，有没有过了的来看看（终于过了）

点我有惊喜！你懂得！

16.求逆序对个数-题解(C++代码)只做最好的思路！

评论区

精彩推荐

简单的a+b （C语言代码）

淘淘的名单 （C语言代码）答案错误？？？

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

众数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

交换Easy （C语言代码）

矩阵的对角线之和 （C语言代码）

1197求助

　　评论区

淘淘的名单（C语言代码）答案错误？？？

众数问题（C语言代码）

C二级辅导-阶乘数列（C语言代码）

矩阵的对角线之和（C语言代码）