【每日一题】3.2 求逆序对

题目描述

给定一个长度为 n的整数数列,请你计算数列中的逆序对的数量。

逆序对的定义如下:对于数列的第 i个和第 j个元素,如果满足 i<j 且 a[i]>a[j],则其为一个逆序对;否则不是。

输入格式
第一行包含整数 n,表示数列的长度。

第二行包含 n个整数,表示整个数列。

输出格式
输出一个整数,表示逆序对的个数。

数据范围 1≤n≤100000,
数列中的元素的取值范围 [1,109]。

输入样例:
6
2 3 4 5 6 1
输出样例:
5

求解

使用归并排序的方法,先分开,在合并的时候判断逆序对数
如要合并下面两个排好序的序列时
在这里插入图片描述
left指向1,right指向2,两者比较,若left指向的数字大于right,则逆序对数= mid - left +1 (因为若left指向的数大于right指向的数,则left之后的数字都大于left指向的数字)

代码

#include<iostream>using namespace std;typedef long long ll;int a[100001];
//int sum =0;void sorta(int a[], int start, int mid, int end, ll* sum){int left = start;int right = mid +1;int j=0;int temp[end - start +1];while(left<= mid && right <= end){//cout<<left<<right<<" "<<a[left]<<a[right]<<endl;if(a[left]>a[right]){//cout<<"sum: "<<*sum<<endl;(*sum)+= mid - left + 1 ;//cout<<mid<<left<<end<<endl;//cout<<"单个排序中:"<<*sum<<endl;temp[j] = a[right];right++;}else{temp[j] = a[left];left++;}j++;}while(left <= mid){temp[j] = a[left];j++;left++;}while(right<= end){temp[j] = a[right];j++;right++;}for(j = 0 ; j< end- start +1 ; j++){a[start + j] = temp[j];}return;}ll merge(int a[], int start, int end){if(start>=end){return 0;}int mid = (start + end)>>1;ll sum =0 ;sum += merge(a, start, mid);sum += merge(a, mid+1, end);//cout<<"排序前"<<start<<" "<<end<<endl;sorta(a,start,mid, end, &sum);//cout<<sum<<endl;return sum;}ll mergesort(int a[], int n){//int sum =0;ll sum = merge(a, 0, n-1);return sum;
}int main(){int n;cin>>n;int i;for(i=0;i <n; i++){cin>>a[i];}ll sum = mergesort(a, n);cout<<sum<<endl;return 0;}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/267655.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Unity 切换场景

场景切换前必须要将场景拖动到Build中 同步加载场景 using System.Collections; using System.Collections.Generic; //using UnityEditor.SearchService; using UnityEngine; // 场景管理 需要导入该类 using UnityEngine.SceneManagement;public class c3 : MonoBehaviour {…

【深度学习笔记】计算机视觉——图像增广

图像增广 sec_alexnet提到过大型数据集是成功应用深度神经网络的先决条件。 图像增广在对训练图像进行一系列的随机变化之后&#xff0c;生成相似但不同的训练样本&#xff0c;从而扩大了训练集的规模。 此外&#xff0c;应用图像增广的原因是&#xff0c;随机改变训练样本可以…

unity 场景烘焙中植物叶片(单面网络)出现的白面

Unity版本 2021.3.3 平台 Windows 在场景烘焙中烘焙植物的模型的时候发现植物的叶面一面是合理的&#xff0c;背面是全白的&#xff0c;在材质球上勾选了双面烘焙&#xff0c;情况如下 这个问题可能是由于植物叶片的单面网格导致的。在场景烘焙中&#xff0c;单面网格只会在一…

【Pytorch】模型部署

文章目录 0. 进行设置1. 获取数据2. FoodVision Mini模型部署实验概要3. 创建 EffNetB2 特征提取器4. 创建 ViT 特征提取器5. 使用训练好模型进行预测并计时6. 比较模型结果、预测时间和大小7. 通过创建 Gradio 演示让 FoodVision Mini 呈现8. 将Gradio demo变成可部署的应用程…

面试准备:排序算法大汇总 C++

排序算法总结 直接插入排序 取出未排序部分的第一个元素&#xff0c;与已排序的部分从后往前比较&#xff0c;找到合适的位置。将大于它的已排序的元素向后移动&#xff0c;将该元素插入到合适的位置。 //1. 直接插入排序 void InsertionSort(vector<int>& nums){f…

Unity 佳能SDK 及数据获取

1. 填写信息跟官方申请SDK,大概1-2个工作日会邮件回复你 佳能(中国)- 佳定制(佳能影像产品),SDK,EDSDK,CCAPI,软件开发包下载 2. 将SDK这两个文件放到 Unity Plugins文件夹 3. 把CameraControl 下面只要是绿色的 .cs 文件都复制到Unity 中

武汉灰京文化:多样化推广与创新引领游戏行业

作为专业的游戏推广服务商&#xff0c;武汉灰京文化注重多样化的推广策略&#xff0c;通过与各大媒体、社交平台和游戏社区建立紧密的合作关系&#xff0c;为游戏企业提供全方位的推广服务。他们通过精确的广告投放、内容创作和社交媒体互动等方式&#xff0c;将游戏信息传播给…

框架漏洞-->Struts2 Docker_Vulnhub搭建

来浅浅的讲一下Struts2漏洞 目录 1.Docker_Vulnhub搭建 2.Struts2 3.Struts2的框架特征 4.S2-029-->Remote Code Execution 5.漏洞复现 1.RCE 2.Getshell 1.Docker_Vulnhub搭建 因为我用的是Linux&#xff0c;所以我选择直接搭个docker&#xff0c;这里我建议先换个…

SpringCloud微服务-统一网关Gateway

统一网关Gateway 文章目录 统一网关Gateway1、为什么需要网关?2、gateway快速入门3、路由断言工厂Route Predicate Factory4、过滤器工厂-路由过滤器GatewayFilter5、全局过滤器**GlobalFilter**6、各种过滤器的执行顺序7、跨域问题的解决 1、为什么需要网关? 网关与各个服务…

模拟队列(数组实现)

题目描述&#xff1a; 代码模板&#xff1a; int q[N],hh,tt -1;//插入操作 void push(int x) {q[tt] x; }//弹出操作 void pop() {hh ; }//判断是否为空 bool empty() {if(hh > tt) return true;else return false; }//返回队首元素 int query() {return q[hh]; }AC代…

【wails】(6):使用wails做桌面应用开发,使用gin+go-chatglm.cpp进行本地模型运行,在windows上运行成功

1&#xff0c;整体架构说明 主要使用&#xff0c;参考的开源项目是&#xff1a; https://github.com/wailsapp/wails 前端项目&#xff1a; https://github.com/Chanzhaoyu/chatgpt-web 运行模型&#xff1a; https://github.com/Weaxs/go-chatglm.cpp 参考代码&#xff1a; h…

React富文本编辑器开发(一)

这是一个系统的完整的教程&#xff0c;每一节文章的内容都很重要。这个教程学完后自己可以开发出一个相当完美的富文本编辑器了。下面就开始我们今天的内容&#xff1a; 安装 是的&#xff0c;我们的开发是基于Slate的开发基础&#xff0c;所以要安装它&#xff1a; yarn ad…

第19章-IPv6基础

1. IPv4的缺陷 2. IPv6的优势 3. 地址格式 3.1 格式 3.2 长度 4. 地址书写压缩 4.1 段内前导0压缩 4.2 全0段压缩 4.3 例子1 4.4 例子 5. 网段划分 5.1 前缀 5.2 接口标识符 5.3 前缀长度 5.4 地址规模分类 6. 地址分类 6.1 单播地址 6.2 组播地址 6.3 任播地址 6.4 例子 …

5GC SBA架构

协议标准&#xff1a;Directory Listing /ftp/Specs/archive/23_series/23.501/ (3gpp.org) NF描述说明NSSFNetwork Slice Selection Function网络切片选择&#xff0c;根据UE的切片选择辅助信息、签约信息等确定UE允许接入的网络切片实例。NEF Network Exposure Function网络开…

在vue2中使用饼状图

1.引入vue2和echarts <script src"https://cdn.jsdelivr.net/npm/vue2.7.14/dist/vue.js"></script> <script src"https://cdn.jsdelivr.net/npm/echarts5.4.0/dist/echarts.min.js"></script> 2.1 补充基本的body内容 <div id…

Vue开发实例(七)Axios的安装与使用

说明&#xff1a; 如果只是在前端&#xff0c;axios常常需要结合mockjs使用&#xff0c;如果是前后端分离&#xff0c;就需要调用对应的接口&#xff0c;获取参数&#xff0c;传递参数&#xff1b;由于此文章只涉及前端&#xff0c;所以我们需要结合mockjs使用&#xff1b;由于…

智慧公厕:让城市更智慧、更环保

在现代社会&#xff0c;智慧公厕作为城市管理的重要一环&#xff0c;是智慧城市的重要组成部分&#xff0c;其建设的价值十出突出&#xff0c;是公共厕所信息化升级改造的核心方案。如智慧公厕源头厂家广州中期科技有限公司&#xff0c;所自主研发的智慧公厕整体解决方案&#…

docker-mysql:5.7安装

1、下载mysql:5.7镜像 [rootlocalhost ~]# docker search mysql (某个XXX镜像名字) [rootlocalhost ~]# docker pull mysql:5.7 按装之前查看一下是否按装过mysql。如果安装过会占用3306端口。 [rootlocalhost ~]# ps -ef | grep mysql 2、安装 # -d&#xff1a;后台运行 #…

VL817-Q7 USB3.0 HUB芯片 适用于扩展坞 工控机 显示器

VL817-Q7 USB3.1 GEN1 HUB芯片 VL817-Q7 USB3.1 GEN1 HUB芯片 VIA Lab的VL817是一款现代USB 3.1 Gen 1集线器控制器&#xff0c;具有优化的成本结构和完全符合USB标准3.1 Gen 1规范&#xff0c;包括ecn和2017年1月的合规性测试更新。VL817提供双端口和双端口4端口配置&…

Go 互斥锁的实现原理?

Go sync包提供了两种锁类型&#xff1a;互斥锁sync.Mutex 和 读写互斥锁sync.RWMutex&#xff0c;都属于悲观锁。 概念 Mutex是互斥锁&#xff0c;当一个 goroutine 获得了锁后&#xff0c;其他 goroutine 不能获取锁&#xff08;只能存在一个写者或读者&#xff0c;不能同时…