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、融进元宇宙,开源…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案
在大数据时代,海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构,在处理大规模数据抓取任务时展现出强大的能力。然而,随着业务规模的不断扩大和数据抓取需求的日益复杂,传统…...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...
Monorepo架构: Nx Cloud 扩展能力与缓存加速
借助 Nx Cloud 实现项目协同与加速构建 1 ) 缓存工作原理分析 在了解了本地缓存和远程缓存之后,我们来探究缓存是如何工作的。以计算文件的哈希串为例,若后续运行任务时文件哈希串未变,系统会直接使用对应的输出和制品文件。 2 …...
