当前位置: 首页 > news >正文

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. 超快速排序 问题描述 分析 这道题考查的算法不难&#xff0c;就只是利用归并排序来求逆序对的数量&#xff0c;但是主要是如何分析问题&#xff0c;如何能从问题中看出来和逆序对数量有关&#xff0c;现在的题目基本上很少是那种模板算法题了&#xff…...

华为、阿里巴巴、字节跳动 100+ Python 面试问题总结(三)

系列文章目录 个人简介&#xff1a;机电专业在读研究生&#xff0c;CSDN内容合伙人&#xff0c;博主个人首页 Python面试专栏&#xff1a;《Python面试》此专栏面向准备面试的2024届毕业生。欢迎阅读&#xff0c;一起进步&#xff01;&#x1f31f;&#x1f31f;&#x1f31f; …...

详解在Linux中修改Tomcat使用的jdk版本

问题分析 由于部署个人项目使用了openjdk11&#xff0c;但是我之前安装的是jdk1.8&#xff0c;jdk版本升级的后果就是&#xff0c;tomcat运行的时候报一点小bug&#xff08;因为之前安装tomcat默认使用了系统的jdk版本&#xff09;所以就想着把tomcat使用的jdk版本调回原来的&…...

高级 Matplotlib:3D 图形和交互性

Matplotlib 是 Python 中最重要的数据可视化库之一。在之前的文章中&#xff0c;我们讨论了如何使用基础和中级功能来创建各种图形。在本文中&#xff0c;我们将深入研究 Matplotlib 的高级特性&#xff0c;特别是如何创建 3D 图形和交互式图形。 一、创建 3D 图形 Matplotli…...

cloud Alibab+nacos+gateway集成swaggerui,统一文档管理(注意点)

首先说明&#xff1a;本文只说整合注意点 效果图和功能参考链接 1.使用gateway访问nacos服务&#xff0c;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&#x1f349; 在线安装依赖环境&#xff1a; yum install gcc yum install socat yum install openssl yum install openssl-devel2. 安装Erlang&#x1f349; 去官网下载一下安装包&#xff0c;将安装包拉到Linux系…...

SAP CAP篇十:理解Fiori UI的Annoation定义

本文目录 本系列此前的文章官方文档和基础概念SAP CAP对Fiori UI的支持package.json的新增内容Annotation定义List Page 生成的Edmx文件 对应代码及branch 本系列此前的文章 SAP CAP篇一: 快速创建一个Service&#xff0c;基于Java的实现 SAP CAP篇二&#xff1a;为Service加上…...

不允许你不知道的 MySQL 优化实战(二)

文章目录 11、使用联合索引时&#xff0c;注意索引列的顺序&#xff0c;一般遵循最左匹配原则。12、对查询进行优化&#xff0c;应考虑在where及order by涉及的列上建立索引&#xff0c;尽量避免全表扫描。13、如果插入数据过多&#xff0c;考虑批量插入。14、在适当的时候&…...

JVM_00000

JVM 所谓虚拟机&#xff08;Virtual Machine&#xff09;就是一台虚拟的计算机。它是一款软件&#xff0c;用来执行一系列虚拟计算机指令。大体上&#xff0c;虚拟机可以分为系统虚拟机和程序虚拟机。 Visual Box&#xff0c;VMware就属于系统虚拟机&#xff0c;它们完全是对物…...

MCU嵌入式开发-硬件和开发语言选择

引入 RTOS的考虑因素 主要考虑以下方面来决定是否需要RTOS支持: 需要实现高响应时的多任务处理能力需要实现实时性能要求高的任务需要完成多个复杂的并发任务 NanoFramework 具备满足工控系统实时性要求的各项功能特性。通过它提供的硬件库、线程支持、中断支持等,可以完全控制…...

SVR算法简介及与其它回归算法的关系

目录 参考链接 有人可以帮助我理解支持向量回归技术和其他简单回归模型之间的主要区别是什么 支持向量回归找到一个线性函数&#xff0c;表示误差范围 (epsilon) 内的数据。也就是说&#xff0c;大多数点都可以在该边距内找到&#xff0c;如下图所示 这意味着 SVR 比大多数其…...

Rust系列(二) 内存管理

上一篇&#xff1a;Rust系列(一) 所有权和生命周期 通过前面的文章&#xff0c;目前我已经了解到了单一所有权、Move语义、Copy语义、可变和不可变借用以及引用计数。突然回首可以发现&#xff0c;Move 语义和 Copy 语义保证了值的单一所有权&#xff1b;而可变和不可变借用又可…...

VYaml | 超快速低内存占用yaml库

一、介绍 官方github仓库 YAML&#xff1a;YAML Ain’t Markup Language&#xff08;YAML 不是标记语言&#xff09;。 使用Unity2021.3 or later。 通过Unity Package Manager安装&#xff1a; https://github.com/hadashiA/VYaml.git?pathVYaml.Unity/Assets/VYaml#0.13.1 …...

动态规划01背包之1049 最后一块石头的重量 II(第9道)

题目&#xff1a; 有一堆石头&#xff0c;用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合&#xff0c;从中选出任意两块石头&#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y&#xff0c;且 。那么粉碎的可能结果如下&#xff1a; …...

运输层(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 主要安排 本帖子专门写给我侄儿&#xff0c;其他读者可以忽略。 步骤一&#xff1a; 跑程序 先下载GDAL&#xff0c;使用的版本号与项目组一致&#xff08;当前使用的版本号为2.2.4&#xff0c;visual studio 2019&#xff09;&#xff1b;百度找到GDAL库的使用教程&#x…...

3.Redis主从复制、哨兵、集群

文章目录 Redis主从复制概念主从复制实验哨兵模式哨兵模式的作用故障转移机制&#xff1a;搭建Redis哨兵模式 Redis集群模式集群的作用搭建Redis集群扩容cluster集 Redis主从复制 概念 Redis主从复制&#xff0c;是指将一台Redis服务器的数据&#xff0c;复制到其他的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 开发者的好时代&#xff0c;有什么理由不多去做一些尝试呢。 北大教授陈钟谈 AI 未来&#xff1a;逼近 AGI、融进元宇宙&#xff0c;开源…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...