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

蓝桥杯练习题——归并排序

1.火柴排队

在这里插入图片描述
在这里插入图片描述

思路

1.求最小值的时候,可以直接按升序排序,这样得到的值就是最小值
2.求最小交换次数的时候,不能直接排序,因为只能交换相邻的数,只需要知道他们的相对大小,所以可以先用离散化,把火柴高度映射成 1 到 n,然后用一个中间数组 c,让 b 数组按照 a 数组的顺序归并排序,交换相邻两个元素,最多只会使得逆序对数量减一
在这里插入图片描述

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10, mod = 99999997;
int a[N], b[N], c[N], d[N];
int n;// 离散化 a 和 b 数组
void init(int q[]){for(int i = 1; i <= n; i++) d[i] = i;// d 数组根据 q 数组的大小关系排序sort(d + 1, d + n + 1, [&](int x, int y){return q[x] < q[y];});for(int i = 1; i <= n; i++) q[d[i]] = i;
}int merge_sort(int l, int r){if(l >= r) return 0;int mid = (l + r) / 2;int res = (merge_sort(l, mid) + merge_sort(mid + 1, r)) % mod;int x = 0, i = l, j = mid + 1;while(i <= mid && j <= r){if(b[i] <= b[j]) d[x++] = b[i++];else{d[x++] = b[j++];res = (res + mid - i + 1) % mod;}}while(i <= mid) d[x++] = b[i++];while(j <= r) d[x++] = b[j++];for(int i = l, j = 0; j < x; i++, j++) b[i] = d[j];return res;
}int main(){scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);for(int i = 1; i <= n; i++) scanf("%d", &b[i]);init(a), init(b);//for(int i = 1; i <= n; i ++ ) cout<<a[i]<<" ";//cout << "a" << endl;//for(int i = 1; i <= n; i ++ ) cout<<b[i]<<" ";//cout << "b" << endl;// c 数组做为中间数组,使得 a 数组是 "有序的",让 b 数组按照 a 数组的顺序进行归并排序for(int i = 1; i <= n; i++) c[a[i]] = i;for(int i = 1; i <= n; i++) b[i] = c[b[i]];//for(int i = 1; i <= n; i ++ ) cout<<b[i]<<" ";//cout << "b" << endl;// 让 b 数组按照 a 数组的顺序进行归并排序int res = merge_sort(1, n);printf("%d", res);return 0;
}

2.归并排序

在这里插入图片描述

思路

模板题

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n;void merge_sort(int l, int r){if(l >= r) return;int mid = (l + r) / 2;merge_sort(l, mid), merge_sort(mid + 1, r);int x = 0, i = l, j = mid + 1;while(i <= mid && j <= r){if(a[i] <= a[j]) b[x++] = a[i++];else b[x++] = a[j++];}while(i <= mid) b[x++] = a[i++];while(j <= r) b[x++] = a[j++];for(int i = l, j = 0; j < x; i++, j++) a[i] = b[j];
}int main(){scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d", &a[i]);merge_sort(0, n - 1);for(int i = 0; i < n; i++) printf("%d ", a[i]);return 0;
}

3.逆序对的数量

在这里插入图片描述

思路

模板题

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n;
long long res;void merge_sort(int l, int r){if(l >= r) return;int mid = (l + r) / 2;merge_sort(l, mid), merge_sort(mid + 1, r);int x = 0, i = l, j = mid + 1;while(i <= mid && j <= r){if(a[i] <= a[j]) b[x++] = a[i++];else{res += 1ll * mid - i + 1;b[x++] = a[j++];}}while(i <= mid) b[x++] = a[i++];while(j <= mid) b[x++] = a[j++];for(int i = l, j = 0; j < x; i++, j++) a[i] = b[j];
}int main(){scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d", &a[i]);merge_sort(0, n - 1);printf("%lld", res);return 0;
}

4.小朋友排队

在这里插入图片描述
在这里插入图片描述

思路

k 队逆序对,最少交换次数就是 k,对于每个数,k1 表示左边有多少个比它大的,k2 表示右边有多少个比它小的,所有数的 k1 和 k2 加起来 >= 2 * k,最小就是 2 * k,也就是逆序对数量的两倍,所以一共交换 1 + 2 + 3 + … + k1 + k2,那么不高兴程度之和就是每个位置的 (1 + k1 + k2) * (k1 + k2) / 2 之和
小朋友要不停的换位置,所以要存储原来的下标

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
pair<int, int> a[N], b[N]; // 存储值和下标
long long sum[N];
int n;void merge_sort(int l, int r){if(l >= r) return;int mid = (l + r) / 2;merge_sort(l, mid), merge_sort(mid + 1, r);int x = 0, i = l, j = mid + 1;while(i <= mid && j <= r){// 加上后面比 a[i] 小的数if(a[i].first <= a[j].first){sum[a[i].second] += j - mid - 1;b[x++] = a[i++];}else{// 加上前面比 a[j] 大的数sum[a[j].second] += mid - i + 1;b[x++] = a[j++];}}while(i <= mid){sum[a[i].second] += j - mid - 1;b[x++] = a[i++];}while(j <= r) b[x++] = a[j++];for(int i = l, j = 0; j < x; i++, j++) a[i] = b[j];
}int main(){scanf("%d", &n);int x;for(int i = 0; i < n; i++){scanf("%d", &x);a[i] = make_pair(x, i);}merge_sort(0, n - 1);long long res = 0;for(int i = 0; i < n; i++) res += (1 + sum[i]) * sum[i] / 2;printf("%lld", res);return 0;
}

5.超快速排序

在这里插入图片描述
在这里插入图片描述

思路

逆序对的数量模板题

#include<iostream>
using namespace std;
const int N = 5e5 + 10;
int a[N], b[N];
int n;
long long res;void merge_sort(int l, int r){if(l >= r) return;int mid = (l + r) / 2;merge_sort(l, mid), merge_sort(mid + 1, r);int x = 0, i = l, j = mid + 1;while(i <= mid && j <= r){if(a[i] <= a[j]) b[x++] = a[i++];else{res += 1ll * mid - i + 1;b[x++] = a[j++];}}while(i <= mid) b[x++] = a[i++];while(j <= mid) b[x++] = a[j++];for(int i = l, j = 0; j < x; i++, j++) a[i] = b[j];
}int main(){while(scanf("%d", &n) && n){for(int i = 0; i < n; i++) scanf("%d", &a[i]);merge_sort(0, n - 1);printf("%lld\n", res);res = 0;}return 0;
}

相关文章:

蓝桥杯练习题——归并排序

1.火柴排队 思路 1.求最小值的时候&#xff0c;可以直接按升序排序&#xff0c;这样得到的值就是最小值 2.求最小交换次数的时候&#xff0c;不能直接排序&#xff0c;因为只能交换相邻的数&#xff0c;只需要知道他们的相对大小&#xff0c;所以可以先用离散化&#xff0c;把…...

C语言--- 指针运算笔试题详解

目录 题目1&#xff1a; 题目2&#xff1a; 题目3&#xff1a; 题目4&#xff1a; 题目5&#xff1a; 题目6&#xff1a; 题目7&#xff1a; 题目1&#xff1a; #include <stdio.h> int main() {int a[5] { 1, 2, 3, 4, 5 };int *ptr (int *)(&a 1);print…...

甘特图是什么,怎么制作?一文让你看懂

甘特图是什么 甘特图是一种项目管理工具&#xff0c;通过图形化的方式直观的能体现出任务、进度和资源在时间里的关系。 白话文就是&#xff1a; 项目分解成了哪些任务?每天计划做什么任务&#xff1f;当前每个任务的进度是多少?项目整体进度是多少&#xff1f;这个项目有…...

mysql笔记:6. 存储引擎

文章目录 查看引擎信息常用引擎介绍InnoDBMyISAMMEMORY存储引擎的选择 数据库存储引擎是数据库底层组件&#xff0c;数据库管理系统使用数据引擎进行创建、查询、更新和删除数据。不同的存储引擎提供不同的存储机制、索引技巧、锁定水平等&#xff0c;使用不同的存储引擎&#…...

(golang)切片何时会创建新切片或影响原切片

什么时候切片操作会影响原切片 // 1.切片后没有触发slice的扩容机制时 什么时候对切片操作会创建新切片不影响原切片 // 2.对切片头元素进行截取的时候 // 3.当使用append时&#xff0c;len > cap则会触发扩容机制 前置&#xff1a; //slice结构体 type SliceHeader struct…...

前端面试——W3C标准及规范

W3C标准 1、万维网联盟标准不是某一个标准&#xff0c;而是一些列标准的集合。 简单来说可以分为结构、表现和行为 结构 主要是有HTML标签组成 表现 即指css样式表 行为 主要是有js、dom组成 web标准一般是将该三部分独立分开&#xff0c;使其更具有模块化。但一般产生行为时&…...

读算法的陷阱:超级平台、算法垄断与场景欺骗笔记07_价格歧视

1. 行为歧视 1.1. 单个企业通过使用数据驱动的算法&#xff0c;从而更好地实现锁定客户、开展个性化营销与定价的目的 1.2. 市场环境再次发生了变化 1.2.1. 在共谋场景中&#xff0c;定价算法提高了企业经营者在销量数据上的透明性&#xf…...

数据结构 之 链表LinkedList

目录 1. ArrayList的缺陷&#xff1a; 2. 链表&#xff1a; 2.1 链表的概念及结构&#xff1a; 3. 链表的使用和模拟实现&#xff1a; 3.1 构造方法&#xff1a; 3.2 模拟实现&#xff1a; 4. 源码分享&#xff1a; 在我学习顺序表之后&#xff0c;我就立马开始了链表的学…...

事务【MySQL】

事务的概念 引入 在 A 转账 100 元给 B 的过程中&#xff0c;如果在 A 的账户已经减去了 100 元&#xff0c;B 的账户还未加上 100 元之前断网&#xff0c;那么这 100 元将会凭空消失。对于转账这件事&#xff0c;转出和转入这两件事应该是绑定在一起的&#xff0c;任意一个动…...

Anaconda 的一些配置

Anaconda 安装及修改环境默认位置 https://blog.csdn.net/qq_54562136/article/details/128932352 最重要的一步&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;改文件夹权限 Anaconda创建、激活、退出、删除虚拟环境 修改pip install 默认安装路径...

利用Nginx正向代理实现局域网电脑访问外网

引言 在网络环境中&#xff0c;有时候我们需要让局域网内的电脑访问外网&#xff0c;但是由于网络策略或其他原因&#xff0c;直接访问外网是不可行的。这时候&#xff0c;可以借助 Nginx 来搭建一个正向代理服务器&#xff0c;实现局域网内电脑通过 Nginx 转发访问外网的需求…...

SpringMVC03、HelloSpring

3、HelloSpring 3.1、配置版 新建一个Moudle &#xff0c; springmvc-02-hello &#xff0c; 添加web的支持&#xff01; 确定导入了SpringMVC 的依赖&#xff01; 配置web.xml &#xff0c; 注册DispatcherServlet <?xml version"1.0" encoding"UTF-8…...

IOS面试题object-c 1-10

1、简述Object-C的理解与特性&#xff1f; OC 作为一门 面向对象 的语言&#xff0c;自然具有面向对象的语言特性&#xff1a;封装、继承、多态。 它既具有 静态语言的特性&#xff08;如C&#xff09;&#xff0c;又有 动态语言的效率&#xff08;动态绑定、动态加载等&#…...

原生JavaScript,根据后端返回扁平JSON动态【动态列头、动态数据】生成表格数据

前期准备&#xff1a; JQ下载地址&#xff1a; https://jquery.com/ <!DOCTYPE html> <html><head><meta charset"utf-8"><title>JSON动态生成表格数据,动态列头拼接</title><style>table {width: 800px;text-align: cen…...

hadoop报错:HADOOP_HOME and hadoop.home.dir are unset. 解决方法

参考&#xff1a;https://blog.csdn.net/weixin_45735242/article/details/120579387 解决方法 1.下载apache-hadoop-3.1.0-winutils-master 官网下载地址&#xff1a; https://github.com/s911415/apache-hadoop-3.1.0-winutils win配置系统环境&#xff1a; 然后重启idea…...

基于Springboot的高校物品捐赠管理系统(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的高校物品捐赠管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系…...

【硬件工程师面经整理29_FPGA】

文章目录 1 nand nor的区别&#xff0c;速度差异的原因&#xff1f;2 nand驱动方式&#xff1f;3 异步信号处理方法4 异步FIFO的深度是如何计算的5 异步复位同步释放的优缺点6 问了FPGA的内部组成&#xff1f;7 LE中查找表的实现原理&#xff1f;8 IOB的主要组成部分&#xff1…...

Ping工作原理

文章目录 目的ping网络协议 OSIICMP什么是ICMP作用功能报文类型查询报文类型差错报文类型ICMP 在 IPv4 和 IPv6 的封装ICMP 在 IPv4 协议中的封装ICMP 在 IPv6 协议中的封装ICMP 头部日常ping 排除步骤ping 查询报文使用code扩展目的 本文主要是梳理ping的工作原理- 揭开 ICMP…...

python调用jar中java方法 静态类为例

java package test;public class test {// run方法返回当前脚本路径public static String runV1(String s) {return "log: " System.getProperty(s);}}python import jpype from jpype import * import osif __name__ "__main__":print(os.environ[JAV…...

tcp服务器客户端通信(socket编程)

目录 1.编程流程 2.代码演示 2.1 服务器代码 2.2 客户端代码 3.注意 3.1 ping命令 3.2 netstat命令 3.3 为什么memset? 3.4 哪个会阻塞? 3.5 显示连接信息 1.概念 1.1 编程流程 1.2 connect与listen connect方法执行后&#xff0c;会进行三次握手&#xff0c;建立连…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...