51Nod 1019 逆序数(归并法求逆序数)

2024-03-06 18:58
文章标签 归并 51nod 序数 法求 1019

本文主要是介绍51Nod 1019 逆序数(归并法求逆序数),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

解题思路:归并算法时间复杂度O(nlogn),排序过程中数据元素的位置交换次数 就是 逆序数。

在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

如2 4 3 1中,2 1,4 3,4 1,3 1是逆序,逆序数是4。给出一个整数序列,求该序列的逆序数。
Input
第1行:N,N为序列的长度(n <= 50000)
第2 - N + 1行:序列中的元素(0 <= A[i] <= 10^9)
Output
输出逆序数
Input示例
4
2
4
3
1
Output示例
4
#include<bits/stdc++.h>
using namespace std;
const int maxn=50000;
int a[maxn],b[maxn];
long long countt;
void merge(int low,int mid,int high)
{int i=low,j=mid+1,k=low;while(i<=mid&&j<=high){if(a[i]<=a[j]){b[k++]=a[i++];}else{b[k++]=a[j++];countt+=mid-i+1;//记录逆序数,当a[i]>a[j]时,表明从i-mid中的所有的数均大于a[j].}}while(i<=mid)b[k++]=a[i++];while(j<=high)b[k++]=a[j++];for(int i=low;i<=high;i++)a[i]=b[i];
}
void merge_sort(int low,int high)
{int mid=(low+high)/2;if(low>=high)return;merge_sort(low,mid);merge_sort(mid+1,high);merge(low,mid,high);
}
int main()
{int n;scanf("%d",&n);countt=0;for(int i=0;i<n;i++)scanf("%d",&a[i]);merge_sort(0,n-1);printf("%lld\n",countt);return 0;
}


      


这篇关于51Nod 1019 逆序数(归并法求逆序数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/781011

相关文章

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客,我们学习了排序算法中的插入排序和选择排序,接下来我们将继续探索交换排序与归并排序,这两个排序都是重头戏,让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换,让较大的元素逐渐向右移动,从而将最大的元素移动到最右边。 动画演示: 1.1.2 具体步

归并排序/计数排序

1:归并排序 1.1:代码 void _MergeSort(int* arr, int left, int right, int* tmp){if (left >= right){return;}int mid = (left + right) / 2; _MergeSort(arr, left, mid, tmp); _MergeSort(arr, mid+1, righ

【SGU】180. Inversions(归并排序求逆序数)

以前一般用树状数组和线段树做这种题 这次换个思路试试,归并排序! #include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int maxn = 111111;int n;int array[maxn];int tmp[maxn];L

归并排序-非递归实现

归并排序的非递归实现  我们可以把 一个数组 先拆分成 最小单元,这是分, 拆分成最小单元之后,我们对每个最小单元进行一次合并,这是治 最小单元 合并一次之后,我们继续 在上一次合并的基础上拆分,并且合并这是 合 , 直到 整个数组 只被拆成了两部分,在进行最终一次的和   我们画图举个例子 源代码如下,我们的merge的合并函数的参数是  原数组,左侧小数组索引位置开头,左侧小数

C# 排序算法之归并排序

归并排序(Merge Sort)是一种分而治之的排序算法。它将一个数组分成两半,对每半部分递归地应用归并排序,然后将排序好的两部分合并成一个有序的数组。归并排序的关键在于合并两个已排序的数组(或数组段)。 以下是归并排序算法的C#实现: using System;class Program{static void Main(string[] args){int[] arr = { 12, 1

MapReduce的shuffle过程详解(分片、分区、合并、归并)

shuffle过程 shuffle概念 shuffle的本意是洗牌、混洗的意思,把一组有规则的数据尽量打乱成无规则的数据。而在MapReduce中,shuffle更像是洗牌的逆过程,指的是将map端的无规则输出按指定的规则“打乱”成具有一定规则的数据,以便reduce端接收处理。其在MapReduce中所处的工作阶段是map输出后到reduce接收前,具体可以分为map端和reduce端前

【51nod】算法马拉松4 F 移数字 【快速求N!%P】【FFT】

传送门:【51nod】算法马拉松4 F 移数字 涉及知识点:多项式求逆,多项式除法,多点插值,阶乘取模。 对于N!%P,复杂度为 O(N−−√log2N−−√) O(\sqrt N \log^2\sqrt N)。 但常数巨大,和暴力算实际复杂度只相差常数= = 这个是可以扩展到组合数取模的~ my  code: my~~code: #include <stdio.h>#includ

归并排序、快速排序c++实现

归并排序 假定由小到大排。 1、思想: 分解:二分为左右两部分; 递归地对两边归并:对左边归并,对右边归并 合并:合并左右为一个。 2、code: 输入: 6 60 90 50 30 20 40 输出: 20 30 40 50 60 90 #include <iostream>#include <vector>using namespace std;//合并v[low...mid]和v[mi

【归并分而治之】逆序对的应对之策

目录 1.前言2.题目简介3.求解思路为什么要这样做?快在哪?为什么这种方法会想到结合归并排序?如何在一左一右中统计剩下的逆序对个数?固定右边的数,用降序会怎么样???思路的本质是巧妙地结合了归并的思想 4.示例代码 1.前言 今天了解到一种比较有意思的题目解法,是专门针对逆序对的。下面来进行简单分享。 2.题目简介 题目链接:LINK 3.求解思路 我们一种解法是

【分治——归并排序】排序数组的归并方法

目录 1.前言2.题目简介3.求解思路4.示例代码 1.前言 今天简单展示一个归并排序解题,难度简单。 2.题目简介 题目链接:LINK 3.求解思路 4.示例代码 //归并排序class Solution {public:vector<int> tmp;vector<int> sortArray(vector<int>& nums) {tmp.resiz