首页 > 其他分享 >逆序对/归并排序

逆序对/归并排序

时间:2024-01-24 16:25:13浏览次数:25  
标签:归并 int mid msort ++ num 排序 逆序

逆序对定义:对于给定的一段正整数序列,逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。

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

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e6+10;
int n,m,a[N],c[N],res,num;
void msort(int l,int r) //归并排序开始
{
    if(l==r) return; //递归终止
    int mid=l+r>>1,i=l,j=mid+1,num=l;
    msort(l,mid),msort(mid+1,r); //确保两边均有序
    while(i<=mid&&j<=r){
        if(a[j]>=a[i]) c[num++]=a[i++];
        else c[num++]=a[j++],res+=mid-i+1; //由于左半部分一定是有序的,所以从i到mid的数都比a[j]大,均为逆序
    }
    while(i<=mid) c[num++]=a[i++];
    while(j<=r) c[num++]=a[j++];
    for(int i=l;i<=r;i++) a[i]=c[i];
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    msort(1,n); //归并排序
    cout<<res;
}

P1774 最接近神的人 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

由于题目要求每次只能交换相邻的 $2$ 个数,最终形成一个不降的序列,所以我们只能把所有逆序的数全部对换即可完成,也就是求出序列的逆序对

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e6+10;
int n,m,a[N],c[N],res,num;
void msort(int l,int r) //归并排序开始
{
    if(l==r) return; //递归终止
    int mid=l+r>>1,i=l,j=mid+1,num=l;
    msort(l,mid),msort(mid+1,r); //确保两边均有序
    while(i<=mid&&j<=r){
        if(a[j]>=a[i]) c[num++]=a[i++];
        else c[num++]=a[j++],res+=mid-i+1; //由于左半部分一定是有序的,所以从i到mid的数都比a[j]大,均为逆序
    }
    while(i<=mid) c[num++]=a[i++];
    while(j<=r) c[num++]=a[j++];
    for(int i=l;i<=r;i++) a[i]=c[i];
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    msort(1,n); //归并排序
    cout<<res;
}

 

标签:归并,int,mid,msort,++,num,排序,逆序
From: https://www.cnblogs.com/o-Sakurajimamai-o/p/17984937

相关文章

  • 逆序句子,但单词顺序不变
    如,输入:Ilikecoding!输出:coding!likeI#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>#include<assert.h>#include<string.h>voidReverse_arr(char*left,char*right){ assert(left); assert(right); chartem=0; while(le......
  • 洛谷题单指南-模拟和高精度-P1786 帮贡排序
    原题链接:https://www.luogu.com.cn/problem/P1786题意解读:此题比较简单,模拟+排序即可解决。需要注意的是,当帮贡或者等级相同时,都要保持原来的顺序,因此需要记录每个人的编号,便于排序。话不多说,直接上代码。100分代码:#include<bits/stdc++.h>usingnamespacestd;constint......
  • 冒泡排序
    冒泡排序//e.g.设计一个函数实现冒泡排序,将一个整型数组排序voidBubble_Sort(int*arr,intsz)//arr是数组,对数组传参,传的是首元素地址&arr[0]{ //确定bubble排序的趟数 inti=0; intcount=0; for(i=0;i<sz-1;i++) { intflag=1; intj=0; for......
  • 用Java实现冒泡排序:实用教程带你入门
    在处理一些特定系统功能时,经常需要使用冒泡排序。例如,在一个电子商务网站中,需要对商品进行排序和过滤。这个时候可以使用冒泡排序对商品进行排序,以便用户能够按照价格、销量、评分等不同字段进行排序。通过使用冒泡排序,系统可以提供更加灵活和个性化的排序选项,以便用户能够更加方便......
  • 冒泡排序、选择排序、二分查找
    1publicstaticvoidmain(String[]args){2//冒泡排序3//定义一个数组,存储一些数据4int[]arr={5,3,1,2,9,6};5System.out.println("=========冒泡排序==========");6//定义一个循环轮数7fo......
  • Layui table 的排序问题
    tableautoSort:falsetabletdsort:true 多页监听排序时间table.on('sort(test)',function(obj){//注:tool是工具条事件名,test是table原始容器的属性lay-filter="对应的值"console.log(obj.field);//当前排序的字段名console.log(obj.type);//当前排序类型:desc(......
  • 问题:以下哪一类材料应按材料内容主次及材料之间联系排序---人力资源部()
    问题:以下哪一类材料应按材料内容主次及材料之间联系排序---人力资源部()A.第二类B.第三类C.第四类D.第五类参考答案如图所示......
  • 归并排序
    归并排序一、核心思想递归;分治;归并二、实现思路1、 相较于快速排序,归并排序将划分区间和排序两个操作在放在不同时间段上,也因此引出了归并的操作。基于此思想————先分再排顺便合并,应当首先使用递归来进行划分,划分标准直接从中间位置划分即可2、 划分之后,对于单个区间......
  • 图论总结——拓扑排序
    图论总结——拓扑排序例\(1\):排水系统(不是很模板的模板题)思路模板题,但是要进行分数约分,所以又不是很模板直接进行计算即可。注意计算过程中很可能爆\(long~~long\)类型范围,需要用\(int128\)类型进行存储。\(Code\)#include<bits/stdc++.h>#defineintlonglongusi......
  • SQL—排序专用窗口函数
    下面介绍三种用于进行排序的专用窗口函数:1、RANK()   在计算排序时,若存在相同位次,会跳过之后的位次。   例如,有3条排在第1位时,排序为:1,1,1,4······2、DENSE_RANK()   这就是题目中所用到的函数,在计算排序时,若存在相同位次,不会跳过之后的位次。   例如,有3......