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

蓝桥杯 5. 交换瓶子

交换瓶子

原题目链接

题目描述

N 个瓶子,编号为 1 ~ N,放在架子上。

例如有 5 个瓶子,当前排列为:

2 1 3 5 4

每次可以拿起 2 个瓶子,交换它们的位置

要求通过若干次交换,使得瓶子的编号从小到大排列为:

1 2 3 4 5

对于简单情况,显然至少需要交换 2 次就能复位。

如果瓶子更多呢?请你编程解决这个问题,找出最少交换次数


输入描述

输入格式为两行:

  • 第一行:一个正整数 N (N < 10⁴),表示瓶子的数目;
  • 第二行:N 个正整数,空格分隔,表示当前瓶子的排列情况。

输出描述

输出一行一个正整数,表示至少交换多少次,才能完成排序。


输入输出样例

示例

输入

5
3 1 2 5 4

输出

3

c++代码

#include<bits/stdc++.h>using namespace std;int N, ans = 0;int main() {cin >> N;vector<int> root(N);for (int i = 0; i < N; i++) cin >> root[i];for (int i = 0; i < N; i++) {while(root[i] != i + 1) {swap(root[i], root[root[i] - 1]);ans++;}}cout << ans;return 0;
}//by wqs

题目解析

贪心算法

我们假设当前的值不对应

说明我们一定要交换

我们要交换次数最小,就要这次交换的利益最大。

如果我们交换一次刚好和可以让两个数同时对应,这样利益最大,贪心的做法也就是和对应值交换

为什么呢,因为这样既可以保证至少有一个可以对应,还有机会可以对应两个。

例如

3 1 2 5 4

1 2 3 4 5

3和1不同,第一个和第三个交换,至少3对应了。

2 1 3 5 4

1 2 3 4 5

2 1 不同,第二个和第一个交换,1和2都对应了。

1 2 3 5 4

1 2 3 4 5

相关文章:

蓝桥杯 5. 交换瓶子

交换瓶子 原题目链接 题目描述 有 N 个瓶子&#xff0c;编号为 1 ~ N&#xff0c;放在架子上。 例如有 5 个瓶子&#xff0c;当前排列为&#xff1a; 2 1 3 5 4每次可以拿起 2 个瓶子&#xff0c;交换它们的位置。 要求通过若干次交换&#xff0c;使得瓶子的编号从小到大…...

本地使用Ollama部署DeepSeek

以下是在本地使用Ollama部署DeepSeek的详细教程&#xff0c;涵盖安装、修改安装目录、安装大模型以及删除大模型的操作步骤。 安装Ollama 1. 系统要求 确保你的系统满足以下条件&#xff1a; 操作系统&#xff1a;macOS、Linux或者Windows。足够的磁盘空间和内存。 2. 安装…...

freecad参数化三维模型装配体解析至web端,切换参数组或修改参数

用免费开源的freecad制作全参数化的三维模型&#xff0c;并且装配&#xff0c;上传至服务器&#xff0c;解析至web端&#xff0c;用户可以切换参数或修改参数&#xff0c;驱动模型改变。 freecad全参数化装配体模型解析至web端进行参数切换、修改完整展示_哔哩哔哩_bilibili …...

前端基础之《Vue(9)—混入》

一、什么是混入 1、是一种代码复用的技巧 Vue组件是由若干选项组成的&#xff0c;向组件中混入可复用的选项。 2、作用 比如我封装两个组件&#xff0c;一个是A组件&#xff0c;一个是B组件&#xff0c;发现它里面有相同的选项&#xff0c;就可以用混用的方式来复用它。 二、…...

ORACLE DATAGUARD遇到GAP增量恢复方式修复RAC环境备机的实践

ORACLE DATAGUARD技术是一个常用的数据保护机制&#xff0c;在DATAGUARD运行过程中&#xff0c;遇到异常导致备机不同步&#xff0c;而主库的归档日志也被清理&#xff0c;此时出现GAP&#xff0c;无法同步&#xff1b;就需要人工处理&#xff1b;对于小型数据库重新全量同步数…...

机器人进阶---视觉算法(六)傅里叶变换在图像处理中怎么用

傅里叶变换在图像处理中怎么用 傅里叶变换的基本原理应用场景Python代码示例逐行解释总结傅里叶变换在图像处理中是一种重要的工具,它将图像从空间域转换到频域,从而可以对图像的频率特性进行分析和处理。傅里叶变换在图像滤波、图像增强、图像压缩和图像分析等方面都有广泛应…...

Java知识日常巩固(五)

Java中wait()和 sleep()的区别? 在Java中,wait()和sleep()方法用于线程控制,但它们之间存在几个关键区别: 1. 用途 wait():用于线程间的协作。当一个线程需要等待某个条件满足时,它会调用wait()方法释放锁并进入等待状态,直到其他线程调用相同对象的notify()或notifyAl…...

浅析锁的应用与场景

锁的应用与场景&#xff1a;从单机到分布式 摘要&#xff1a;在多线程和分布式系统中&#xff0c;“锁”是避免资源竞争、保障数据一致性的核心机制。但你真的了解锁吗&#xff1f;什么时候该用锁&#xff1f;用哪种锁&#xff1f;本文通过通俗的比喻和代码示例&#xff0c;带…...

语音合成之五语音合成中的“一对多”问题主流模型解决方案分析

语音合成中的“一对多”问题主流模型解决方案分析 引言“一对多”指的是什么&#xff1f;优秀开源模型的方法CosyvoiceSparkTTSLlaSA TTSVITS 引言 TTS系统旨在模仿人类的自然语音&#xff0c;但其核心面临着一个固有的挑战&#xff0c;即“一对多”问题 。这意味着对于给定的…...

ElementUi的Dropdown下拉菜单的详细介绍及使用

Dropdown是 ElementUI 中用于创建下拉菜单项的一个组件&#xff0c;通常el-dropdown-item 包裹在 el-dropdown 组件中使用。以下从功能特性(一些属性及方法)、使用和高级功能(高亮显示&#xff0c;滚动&#xff0c;额外传参数)三个方面进行详细介绍。 一、功能特性 1.触发方式…...

Linux麒麟 V10 系统找回 root 密码的步骤

Linux麒麟 V10 系统找回 root 密码的步骤 1 环境介绍2 操作步骤2.1重启系统并进入 GRUB 菜单2.2 输入 GRUB 账户密码2.3 修改启动参数2.4 启动系统2.5 修改root 密码2.6 重启系统 3 Linux命令全方位指南实战教程Linux命令学习使用列表 1 环境介绍 有时候root 密码忘记&#xf…...

20、 DeepSeekMoE论文笔记

DeepSeekMoE 1、**研究背景与动机**2、传统MoE一、MoE架构核心原理详解1. **标准Transformer块的结构**2. **MoE层对FFN的替代**3. **稀疏性与计算效率** 二、举例说明&#xff1a;以 N 4 N4 N4 专家、 K 2 K2 K2 为例1. **场景设定**2. **亲和度计算与专家选择**3. **输出计…...

在 Spring Boot 中实现 WebSockets

什么是 WebSockets&#xff1f; WebSockets 是一种基于 TCP 的全双工通信协议&#xff0c;允许客户端和服务器之间建立持久的双向连接&#xff0c;用于实时数据交换。相较于传统的 HTTP 请求-响应模型&#xff0c;WebSockets 提供了低延迟、高效率的通信方式&#xff0c;特别适…...

stone 3d v3.3.0版本发布,含时间线和连接器等新功能

1.新加了时间线&#xff08;timeline&#xff09;编辑器&#xff0c;可以类似blender一样给对象制作动画 2.新加了度量&#xff08;metrics&#xff09;系统&#xff0c;通过scene对象检测器中的useMetrics属性来启用或禁用&#xff0c;启用时所选物体将显示三维度量数据 新加了…...

.whl文件

本文主要介绍了.whl文件的定义&#xff0c;怎么安装.whl文件&#xff08;离线&#xff0c;在线&#xff09;。 怎么查看cuda的版本&#xff0c;以及如何安装相应版本的cuda&#xff08;本地电脑&#xff0c;超算上&#xff09; 以及如何创建.whl文件 .whl文件的定义 Document…...

Git命令行中vim的操作

Git命令行用vim打开文件&#xff0c;或者用其他git命令打开了文件&#xff0c;需要编辑和保存文件等&#xff0c;有些命令表情奇怪&#xff0c;往往容易忘记这些命令。记录下。 下面这篇比较实用和简练&#xff1a; gitvim编辑文件命令 • Worktile社区https://worktile.com/…...

C#初级知识总结

一、什么是CIL 1.CIL(Common Intermidate Language)是指.Net的公共中间语言&#xff0c;它是一种编程语言。 .Net框架的各种语言在编译时都会编译成同一种中间语言&#xff08;CIL&#xff09;&#xff0c;之后程序运行的时候CIL会被JIT(Just In Time)转换为二进制语言&#xf…...

使用 AI Agent 改善师生互动的设计文档

使用 AI Agent 改善师生互动的设计文档 一、引言 1.1 研究背景 当前教育领域的师生互动存在诸多挑战&#xff0c;如教师负担过重、学生个体差异大导致难以满足所有人的需求&#xff0c;以及信息传递延迟等问题。引入AI-Agent能够有效缓解这些问题&#xff0c;通过自动化手段协…...

Linux学习笔记之环境变量

写这篇博客的目的主要是因为本人学习动静态库时&#xff0c;用到了环境变量的知识&#xff0c;发现略有遗忘&#xff0c;因此回顾复习&#xff0c;整理成博客。 一、环境变量是什么 Linux环境变量是存储系统或程序运行时配置信息的特殊变量&#xff0c;用于为程序提供配置参数…...

16:00开始面试,16:08就出来了,问的问题有点变态。。。

从小厂出来&#xff0c;没想到在另一家公司又寄了。 到这家公司开始上班&#xff0c;加班是每天必不可少的&#xff0c;看在钱给的比较多的份上&#xff0c;就不太计较了。没想到4月一纸通知&#xff0c;所有人不准加班&#xff0c;加班费不仅没有了&#xff0c;薪资还要降40%…...

深度解析云计算:概念、优势与分类全览

以下是对云计算概念、优点和分类更详细的介绍&#xff1a; 一、云计算的概念 云计算是一种通过互联网提供计算服务的模式&#xff0c;它基于虚拟化、分布式计算、网络存储等一系列先进技术&#xff0c;将计算资源进行整合和管理&#xff0c;形成一个庞大的资源池。这些资源包…...

私钥连接服务器(已经有服务器私钥

前言&#xff1a;假设我们已经有了服务器的私钥&#xff0c;我们怎么配置呢&#xff1f; 下面我会从vsc的配置角度来写 ✅ 步骤一&#xff1a;准备工作 安装 VS Code&#xff08;如果还没装&#xff09; &#x1f449; https://code.visualstudio.com/ 安装插件&#xff1a;Re…...

学员答题pk知识竞赛小程序怎么做

制作学员答题PK知识竞赛小程序&#xff0c;主要有以下步骤&#xff1a; 一、规划设计 明确需求&#xff1a;确定小程序的使用场景是校园知识竞赛、培训机构考核还是企业内部培训等。答题功能&#xff0c;规定答题的具体规则&#xff0c;包括题目类型&#xff08;单选、多选、…...

外观模式:简化复杂系统接口的设计模式

外观模式&#xff1a;简化复杂系统接口的设计模式 一、模式核心&#xff1a;为复杂子系统提供统一简单接口 当一个系统由多个复杂子系统组成时&#xff08;如电商系统中的支付、物流、库存模块&#xff09;&#xff0c;客户端直接调用子系统会导致依赖关系复杂、代码难以维护…...

vue3项目中eslint.config.ts配置rules

vue3项目中eslint.config.ts配置rules 1. 使用npm create vuelatest创建vue项目 默认的eslint.config.ts如下 import { globalIgnores } from eslint/config import { defineConfigWithVueTs, vueTsConfigs } from vue/eslint-config-typescript import pluginVue from esli…...

uniapp-商城-36-shop 购物车 选好了 进行订单确认2 支付方式颜色变化和颜色滤镜filter

颜色滤镜&#xff0c;在好多网页都这样使用&#xff0c;滤掉彩色&#xff0c;显示黑白&#xff0c;这在一些关键的日子中都这样使用。 1、依然回到订单确认页面 看到支付的颜色了嘛&#xff1f; <view class"payType"><view class"box" :class&q…...

Vue3 上传后的文件智能预览(实战体会)

目录 前言1. Demo12. Demo2 前言 &#x1f91f; 找工作&#xff0c;来万码优才&#xff1a;&#x1f449; #小程序://万码优才/r6rqmzDaXpYkJZF 爬虫神器&#xff0c;无代码爬取&#xff0c;就来&#xff1a;bright.cn 此处的基本知识涉及较少&#xff0c;主要以Demo的形式供大…...

铃木一郎女儿是奥运会选手吗·棒球1号位

铃木一朗&#xff08;Ichiro Suzuki&#xff09; 铃木一朗职业生涯时间线 1973年出生于日本爱知县名古屋市。1992年以选秀第四顺位加入日本职棒&#xff08;NPB&#xff09;欧力士蓝浪队&#xff0c;开启职业棒球生涯。 1994-2000年 连续7年获得NPB太平洋联盟打击王&#xff…...

PyTorch与CUDA的关系

文章目录 前言一、如何查看PyTorch和torchvision的版本1.1 查看PyTorch版本1.2 查看torchvision版本二、如何确认PyTorch和torchvision是否支持CUDA加速2.1 检查PyTorch是否支持CUDA2.2 查看当前可用的GPU设备2.3 检查torchvision是否支持CUDA三、CUDA版本的秘密:为什么PyTorc…...

CCE13.【C++ Cont】练习题组13 静态链表专题

目录 1.B3630 排队顺序 题目 分析 代码 提交结果 2.B3631 单向链表 题目 分析 前置知识:map数组加快访问速度(简单的哈希表优化) 使用map数组的重要提醒 代码 提交结果 3.★P1160 队列安排 题目 分析 方法1:带头不循环双向链表的设计 方法2:带头循环的双向链表…...