AcWing 107. 超快速排序—逆序对
问题链接: AcWing 107. 超快速排序
问题描述

分析
这道题考查的算法不难,就只是利用归并排序来求逆序对的数量,但是主要是如何分析问题,如何能从问题中看出来和逆序对数量有关,现在的题目基本上很少是那种模板算法题了,更注重思维,所以一定要培养好思维,模板只是基础。
这道题交换相邻的两个数,首先会先想到冒泡排序,冒泡排序就是交换相邻的两个数,这道题用冒泡排序也能做,但是冒泡排序时间复杂度是 O ( n 2 ) O(n^2) O(n2)的,肯定过不了。我们思考冒泡排序在什么情况下会交换两个相邻的数,目标是升序序列时,当f[i]>f[i+1]时,会交换f[i]与f[i+1],交换后可以发现f[i]的逆序对数量减少了一个,所以就能往这方面想,最后可以发现逆序对的数量就是需要交换的最少次数。
思维很重要,或者说在熟知算法模板的情况下,更重要的就是思维了。
代码如下
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=5e5+10;ll f[N];
ll tmp[N];
ll n,k;
void merge_sort(int l,int r){if(l>=r) return;int mid=l+r>>1;merge_sort(l,mid);merge_sort(mid+1,r);int i=l,j=mid+1,t=0;while(i<=mid&&j<=r)if(f[i]<=f[j]) tmp[t++]=f[i++];else{tmp[t++]=f[j++];k+=mid-i+1;} while(i<=mid) tmp[t++]=f[i++];while(j<=r) tmp[t++]=f[j++];for(int i=l;i<=r;i++) f[i]=tmp[i-l];
}
int main(){while(~scanf("%d",&n)&&n){for(int i=0;i<n;i++) scanf("%lld",&f[i]);k=0;merge_sort(0,n-1);printf("%lld\n",k);}return 0;
}
相关文章:
AcWing 107. 超快速排序—逆序对
问题链接: AcWing 107. 超快速排序 问题描述 分析 这道题考查的算法不难,就只是利用归并排序来求逆序对的数量,但是主要是如何分析问题,如何能从问题中看出来和逆序对数量有关,现在的题目基本上很少是那种模板算法题了ÿ…...
华为、阿里巴巴、字节跳动 100+ Python 面试问题总结(三)
系列文章目录 个人简介:机电专业在读研究生,CSDN内容合伙人,博主个人首页 Python面试专栏:《Python面试》此专栏面向准备面试的2024届毕业生。欢迎阅读,一起进步!🌟🌟🌟 …...
详解在Linux中修改Tomcat使用的jdk版本
问题分析 由于部署个人项目使用了openjdk11,但是我之前安装的是jdk1.8,jdk版本升级的后果就是,tomcat运行的时候报一点小bug(因为之前安装tomcat默认使用了系统的jdk版本)所以就想着把tomcat使用的jdk版本调回原来的&…...
高级 Matplotlib:3D 图形和交互性
Matplotlib 是 Python 中最重要的数据可视化库之一。在之前的文章中,我们讨论了如何使用基础和中级功能来创建各种图形。在本文中,我们将深入研究 Matplotlib 的高级特性,特别是如何创建 3D 图形和交互式图形。 一、创建 3D 图形 Matplotli…...
cloud Alibab+nacos+gateway集成swaggerui,统一文档管理(注意点)
首先说明:本文只说整合注意点 效果图和功能参考链接 1.使用gateway访问nacos服务,503 在网关服务添加依赖即可解决 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-openfeign&…...
使用 YOLOv8 进行传输线故障检测-附源码
用于传输线故障检测的 YOLO 我将模型缩小到YOLO 或 Faster R-CNN。但YOLO 作为单次目标检测模型在速度和计算效率方面获得了许多好处。由于基于无人机的实时故障检测是最佳选择,我选择使用 YOLO。YOLO 代表“You Only Look Once”,暗示您只需要通过一个神经网络即可对检测到…...
安装RabbitMQ 详细步骤
我这里是在Linux系统里面安装的按照步骤即可 1. 安装Socat🍉 在线安装依赖环境: yum install gcc yum install socat yum install openssl yum install openssl-devel2. 安装Erlang🍉 去官网下载一下安装包,将安装包拉到Linux系…...
SAP CAP篇十:理解Fiori UI的Annoation定义
本文目录 本系列此前的文章官方文档和基础概念SAP CAP对Fiori UI的支持package.json的新增内容Annotation定义List Page 生成的Edmx文件 对应代码及branch 本系列此前的文章 SAP CAP篇一: 快速创建一个Service,基于Java的实现 SAP CAP篇二:为Service加上…...
不允许你不知道的 MySQL 优化实战(二)
文章目录 11、使用联合索引时,注意索引列的顺序,一般遵循最左匹配原则。12、对查询进行优化,应考虑在where及order by涉及的列上建立索引,尽量避免全表扫描。13、如果插入数据过多,考虑批量插入。14、在适当的时候&…...
JVM_00000
JVM 所谓虚拟机(Virtual Machine)就是一台虚拟的计算机。它是一款软件,用来执行一系列虚拟计算机指令。大体上,虚拟机可以分为系统虚拟机和程序虚拟机。 Visual Box,VMware就属于系统虚拟机,它们完全是对物…...
MCU嵌入式开发-硬件和开发语言选择
引入 RTOS的考虑因素 主要考虑以下方面来决定是否需要RTOS支持: 需要实现高响应时的多任务处理能力需要实现实时性能要求高的任务需要完成多个复杂的并发任务 NanoFramework 具备满足工控系统实时性要求的各项功能特性。通过它提供的硬件库、线程支持、中断支持等,可以完全控制…...
SVR算法简介及与其它回归算法的关系
目录 参考链接 有人可以帮助我理解支持向量回归技术和其他简单回归模型之间的主要区别是什么 支持向量回归找到一个线性函数,表示误差范围 (epsilon) 内的数据。也就是说,大多数点都可以在该边距内找到,如下图所示 这意味着 SVR 比大多数其…...
Rust系列(二) 内存管理
上一篇:Rust系列(一) 所有权和生命周期 通过前面的文章,目前我已经了解到了单一所有权、Move语义、Copy语义、可变和不可变借用以及引用计数。突然回首可以发现,Move 语义和 Copy 语义保证了值的单一所有权;而可变和不可变借用又可…...
VYaml | 超快速低内存占用yaml库
一、介绍 官方github仓库 YAML:YAML Ain’t Markup Language(YAML 不是标记语言)。 使用Unity2021.3 or later。 通过Unity Package Manager安装: https://github.com/hadashiA/VYaml.git?pathVYaml.Unity/Assets/VYaml#0.13.1 …...
动态规划01背包之1049 最后一块石头的重量 II(第9道)
题目: 有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 。那么粉碎的可能结果如下: …...
运输层(TCP运输协议相关)
运输层 1. 运输层概述2. 端口号3. 运输层复用和分用4. 应用层常见协议使用的运输层熟知端口号5. TCP协议对比UDP协议6. TCP的流量控制7. TCP的拥塞控制7.1 慢开始算法、拥塞避免算法7.2 快重传算法7.3 快恢复算法 8. TCP超时重传时间的选择8.1 超时重传时间计算 9. TCP可靠传输…...
GDAL操作实践培训
1 主要安排 本帖子专门写给我侄儿,其他读者可以忽略。 步骤一: 跑程序 先下载GDAL,使用的版本号与项目组一致(当前使用的版本号为2.2.4,visual studio 2019);百度找到GDAL库的使用教程&#x…...
3.Redis主从复制、哨兵、集群
文章目录 Redis主从复制概念主从复制实验哨兵模式哨兵模式的作用故障转移机制:搭建Redis哨兵模式 Redis集群模式集群的作用搭建Redis集群扩容cluster集 Redis主从复制 概念 Redis主从复制,是指将一台Redis服务器的数据,复制到其他的Redis服务…...
Windows电源模式(命令行)
一、简介 windows使用powercfg.exe来控制电源方案,像cmd.exe一样,powercfg.exe也是windows自带的。 powercfg命令行选项 选项说明/?、-help显示有关命令行参数的信息。/list、/L列出所有电源方案。/query、/Q显示电源方案的内容。...
6月份读书学习好文记录
看看CHATGPT在最近几个月的发展趋势 https://blog.csdn.net/csdnnews/article/details/130878125?spm1000.2115.3001.5927 这是属于 AI 开发者的好时代,有什么理由不多去做一些尝试呢。 北大教授陈钟谈 AI 未来:逼近 AGI、融进元宇宙,开源…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...
HTTPS证书一年多少钱?
HTTPS证书作为保障网站数据传输安全的重要工具,成为众多网站运营者的必备选择。然而,面对市场上种类繁多的HTTPS证书,其一年费用究竟是多少,又受哪些因素影响呢? 首先,HTTPS证书通常在PinTrust这样的专业平…...
如何做好一份技术文档?从规划到实践的完整指南
如何做好一份技术文档?从规划到实践的完整指南 🌟 嗨,我是IRpickstars! 🌌 总有一行代码,能点亮万千星辰。 🔍 在技术的宇宙中,我愿做永不停歇的探索者。 ✨ 用代码丈量世界&…...
