108叶先毅是个小蒟蒻

用户名：dotcpp0787179

访问量：93

签　名：

榜二别卷了！

等　　级
排　　名	7517
经　　验	1284
参赛次数	0
文章发表	18
年　　龄	1
在职情况	学生
学　　校	内江师范学院
专　　业	纳西妲系

　　自我简介：

那是纳西妲吗？

TA的其他文章

bfs之八数码问题/一维化二维思路--蓝桥杯省赛2023
浏览：8

必备技法--高精加//vector数组版 + string版
浏览：10

必备技法--高精度乘法//vector版
浏览：7

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）（答案错误解析）

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

The 3n + 1 problem （C++代码）（所有测试数据都小于等于1000，，说好的1000000之内呢）

利用归并排序求逆序对--模版题

　　作者: 108叶先毅是个小蒟蒻　　　　发表时间：2024-09-12 11:34:43 浏览：22　|　评论：3　

原题链接：信息学奥赛一本通T1311-求逆序对

# 归并排序求逆序对 时间复杂O(nlog(n))

第一次在这个平台发题解 本蒟蒻有点紧张哈哈哈 这是一个模版 背住就行 需要注意几个地方 递归时的左右边界需要注意不要越界，。

详细看代码块注释

###### Code：
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long //个人习惯 被坑多了自然就习惯了

using namespace std;
const int N = 1e5 + 5;
int n , a[N] , ans , temp[N]; // 需要开两个数组 一个存排序后的 一个为中间状态存贮
void merge_sort(int l , int r) // l为左边界 ， r为右边界
{
    if (l >= r) return ; //当 l == r时 即排序完成
    int mid = l + r >> 1;
    
    merge_sort(l , mid) , merge_sort(mid + 1 , r); //递归

int i = l , j = mid + 1 , k = 0;

while (i <= mid && j <= r)
    {
        if (a[i] <= a[j]) temp[k ++ ] = a[i ++ ];
        else 
        {
            temp[k ++ ] = a[j ++ ];
            ans += mid - i + 1;  //记录逆序对的数量 
        }
    }

while (i <= mid) temp[k ++ ] = a[i ++ ]; // 检查剩余元素有无遗漏
    while (j <= r) temp[k ++ ] = a[j ++ ];

for (int i = l , j = 0 ; i <= r ; j ++ , i ++  ) a[i] = temp[j]; //每次排序完成后 需要还原数组
    
}
signed main() // 个人习惯 同 int 
{
    cin >> n;

for (int i = 1 ; i <= n ; i ++ ) cin >> a[i];

merge_sort(1 , n);  // 归并排序入口

cout << ans << endl;

return 0;
}
```

0.0分

4 人评分

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

　　评论区

109徐守佳

while(true) putchar("%");

2024-09-12 13:14:33

036叶洪鑫

牛呀 哥

2024-09-12 13:07:21

108叶先毅是个小蒟蒻

点点赞 点点赞

2024-09-12 11:35:58

108叶先毅是个小蒟蒻

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）（答案错误解析）

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

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

The 3n + 1 problem （C++代码）（所有测试数据都小于等于1000，，说好的1000000之内呢）

IP判断（C语言代码）

利用归并排序求逆序对--模版题

评论区

精彩推荐

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

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

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

回文串（C语言代码）

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

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

本人酷爱递归实现很多问题，这里也是

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

【计算两点间的距离】（C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

108叶先毅是个小蒟蒻

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）（答案错误解析）

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

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

The 3n + 1 problem （C++代码）（所有测试数据都小于等于1000，，说好的1000000之内呢）

IP判断 （C语言代码）

利用归并排序求逆序对--模版题

评论区

精彩推荐

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

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

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

回文串 （C语言代码）

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

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

本人酷爱递归实现很多问题，这里也是

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

【计算两点间的距离】 （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

IP判断（C语言代码）

　　评论区

回文串（C语言代码）

【计算两点间的距离】（C语言代码）