AcWing 1224 交换瓶子(简单图论)

[题目概述]

有 N 个瓶子,编号 1∼N,放在架子上。
比如有 5 个瓶子:
2 1 3 5 4
要求每次拿起 2 个瓶子,交换它们的位置。
经过若干次后,使得瓶子的序号为:
1 2 3 4 5
对于这么简单的情况,显然,至少需要交换 2 次就可以复位。
如果瓶子更多呢?你可以通过编程来解决。

输入格式

第一行包含一个整数 N,表示瓶子数量。
第二行包含 N 个整数,表示瓶子目前的排列状况。

输出格式

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

数据范围

1 ≤ N ≤ 10000 , 1 ≤ N ≤ 10000, 1N10000,

输入样例1:

5
3 1 2 5 4

输出样例1:

3

输入样例2:

5
5 4 3 2 1

输出样例2:

2

我们可以将一个瓶子看成一个点,它与其正确位置上的瓶子序号连线就构成了图
拿样例画一下
正确位置:1 2 3 4 5
现在位置:3 1 2 5 4
现在第一个位置的3指向3号位置对应的2,然后2指向2号对应位置的1号瓶子,1指向1号位置对应的3号瓶子,这样先构成了第一个环;5指向5号位置的4号瓶子,4指向4号位置的5号瓶子。

请添加图片描述

现在我们需要交换顺序了
分为两种情况,同一个环内的两个点交换,不同环内的点交换
1.同一个环内的两个点交换
假设交换2和3
正确位置:1 2 3 4 5
现在位置:2 1 3 5 4
请添加图片描述
变成了3个环
2.不同环之间交换
假设交换1和5
正确位置:1 2 3 4 5
现在位置:3 5 2 1 4
请添加图片描述
两个环合成了一个环

理想状态是
正确位置:1 2 3 4 5
现在位置:1 2 3 4 5
也就是五个环,所以我们现在要增加3个环,也就是进行3次操作
那么原来有k个环,我们就要进行n-k次操作,现在就是要求一共有几个环。

  • 完整代码
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 10005;
int b[N]; // 记录每个位置放的哪个瓶子
bool st[N]; // 记录每个瓶子是否被用过(判断环)
int n;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> b[i];
	}

	int k = 0;
	for (int i = 1; i <= n; i ++) {
		// 一个环的开始
		if (!st[i]) {
			k ++;
			// 一个环接下来的所有点
			// j的更新在下面解释
			for (int j = i; !st[j]; j = b[j]) {
				st[j] = true;
			}
		}
	}

	cout << n - k << endl;
	return 0;
}

j的更新解释
请添加图片描述

  • 本题的分享就结束了,这是我第一次接触图论的题,第一步就很难想出来。慢慢来吧
    别忘了点赞关注加收藏!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/380244.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Linux命令行工具使用HTTP代理的方法详解

亲爱的Linux用户们&#xff0c;有没有想过在命令行世界里&#xff0c;你的每一个指令都能悄无声息地穿越千山万水&#xff0c;而不被外界窥探&#xff1f;哈哈&#xff0c;没错&#xff0c;就是通过HTTP代理&#xff01;今天&#xff0c;我们就来一起探索如何在Linux命令行工具…

林浩然与杨凌芸的Java奇遇记:Lambda表达式大冒险

林浩然与杨凌芸的Java奇遇记&#xff1a;Lambda表达式大冒险 Lin Haoran and Yang Lingyun’s Java Adventure: The Grand Expedition of Lambda Expressions 在Java编程世界的一隅&#xff0c;住着一对编程界的“才子佳人”&#xff0c;男主角名叫林浩然&#xff0c;女主角唤作…

【Algorithms 4】算法(第4版)学习笔记 06 - 2.3 快速排序

文章目录 前言参考目录学习笔记1&#xff1a;基本算法1.1&#xff1a;快速排序 demo 演示1.2&#xff1a;快速排序切分代码实现1.3&#xff1a;实现细节1.4&#xff1a;案例分析1.4.1&#xff1a;最佳案例1.4.2&#xff1a;最坏案例1.4.3&#xff1a;平均案例分析1.5&#xff1…

从Kafka系统中读取消息数据——消费

从Kafka系统中读取消息数据——消费 消费 Kafka 集群中的主题消息检查消费者是不是单线程主题如何自动获取分区和手动分配分区subscribe实现订阅&#xff08;自动获取分区&#xff09;assign&#xff08;手动分配分区&#xff09; 反序列化主题消息反序列化一个类.演示 Kafka 自…

大模型学习 一

https://www.bilibili.com/video/BV1Kz4y1x7AK/?spm_id_from333.337.search-card.all.click GPU 计算单元多 并行计算能力强 指数更重要 A100 80G V100 A100 海外 100元/时 单卡 多卡并行&#xff1a; 单机多卡 模型并行 有资源的浪费 反向传播 反向传播&#xff08;B…

通过遵循最佳做法来提高 EDA 和 HPC 应用程序的 Azure NetApp 文件性能

介绍 Azure NetApp 文件是一项托管存储解决方案&#xff0c;适用于各种方案&#xff0c;包括高性能计算 (HPC) 基础结构。 低延迟和每秒高 I/O 操作数 (IOPS) 对于大规模企业而言是一种很好的组合。 假设你就职于一家半导体公司。 你的任务是设计公司的集成电路芯片&#xff…

Ajax+JSON学习一

AjaxJSON学习一 文章目录 前言一、Ajax简介1.1. Ajax基础1.2. 同源策略 二、Ajax的核心技术2.1. XMLHttpRequest 类2.2. open指定请求2.3. setRequestHeader 设置请求头2.4. send发送请求主体2.5. Ajax取得响应 总结 前言 一、Ajax简介 1.1. Ajax基础 Ajax 的全称是 Asynchron…

【项目问题解决】java. net.SocketException: Connection reset

目录 【项目问题解决】java. net.SocketException: Connection reset 1.问题描述2.问题原因3.解决思路4.解决方案5.总结6.参考 文章所属专区 项目问题解决 1.问题描述 通过JMeter 压测接口&#xff0c;无并发&#xff0c;无间歇时间跑接口10000次报错&#xff0c;后续改成建个…

DBdoctor恭祝大家龙行龘龘,前程朤朤

值此新年之际&#xff0c;DBdoctor恭祝大家龙行龘龘&#xff0c;前程朤朤。尤其是当前还跟我一样奋斗在护航春节一线的战友们&#xff0c;祝愿大家2024年系统又快又稳。 今年是DBdoctor护航春晚的第三年&#xff0c;聚好看作为海信旗下的互联网科技公司&#xff0c;服务着海信…

再识C语言 DAY17 【什么是原码、反码和补码】

文章目录 前言本文总结于此文章 一、知识补充二、原码三、反码四&#xff0c;补码 总结如果您发现文章有错误请与我留言&#xff0c;感谢 前言 本文总结于此文章 一、知识补充 通常&#xff0c;1字节包含8位。C语言用字节&#xff08;byte&#xff09;表示储存系统字符集所需…

导入jar包的办法,若Maven报日志错误,Cannnot resolve XXXXX.jar

相信很多人在进行涉及到java工程项目&#xff0c;都会遇到很多问题&#xff0c;在pom文件中导入jar包&#xff0c;或许会出现cannot resolve XXXXX的问题&#xff0c;从而会报个别的错误。 接下来我将介绍两种导入jar包的方法 导入jar包&#xff0c;从官网直接下载下来相关的…

国产光耦2024:发展机遇与挑战全面解析

随着科技的不断进步&#xff0c;国产光耦在2024年正面临着前所未有的机遇与挑战。本文将深入分析国产光耦行业的发展现状&#xff0c;揭示其在技术创新、市场需求等方面的机遇和挑战。 国产光耦技术创新的机遇&#xff1a; 国产光耦作为光电器件的重要组成部分&#xff0c;其技…

Flume安装部署

安装部署 安装包连接&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1m0d5O3Q2eH14BpWsGGfbLw?pwd6666 &#xff08;1&#xff09;将apache-flume-1.10.1-bin.tar.gz上传到linux的/opt/software目录下 &#xff08;2&#xff09;解压apache-flume-1.10.1-bin.tar.gz…

mysql 中文编码问题

前言 最近在学springboot整合mybatisplus技术&#xff0c;用到mysql数据库&#xff0c;然后发现在windows下插入数据表会出现中文乱码现象 (例如 “我是谁” 在数据库中就成了 “???”) windows show variables like %char%;建表时, 设置默认charset为gbk create table u…

linux系统定时任务管理

crontab使用 一、crontab简介 crontab 这个指令所设置的工作将会循环的一直进行下去&#xff01;可循环的时间为分钟、小时、每周、每月或每年等。crontab 除了可以使用指令执行外&#xff0c;亦可编辑 /etc/crontab 来支持。 至于让 crontab 可以生效的服务则是 crond 这个服…

InternLM大模型实战-1.书生浦语大模型全链路开源体系

文章目录 前言笔记正文大模型成为热门关键词书生浦语开源历程从模型到应用书生浦语全链条开源开放体系数据预训练微调评测部署部署智能体LagentAgentLego 总结 前言 本系列文章是参与书生浦语全链路开源体系学习的笔记文章。B站视频教程地址&#xff1a; 笔记正文 大模型成为…

【玩转408数据结构】线性表——定义和基本操作

考点剖析 线性表是算法题命题的重点&#xff0c;该类题目实现相对容易且代码量不高&#xff0c;但需要最优的性能&#xff08;也就是其时间复杂度以及空间复杂度最优&#xff09;&#xff0c;这样才可以获得满分。所以在考研复习中&#xff0c;我们需要掌握线性表的基本操作&am…

vue3集成bpmn

文章目录 前言一、依赖二、汉化配置1.引入文件2.样式文件 总结 前言 vue3 集成bpmn 配置工作流 一、依赖 "bpmn-js": "^7.3.1", "bpmn-js-properties-panel": "^0.37.2", "bpmn-moddle": "^6.0.0", "camu…

MySQL 主键策略导致的效率性能

MySQL官方推荐不要使用uuid或者不连续不重复的雪花id(long形且唯一)&#xff0c;而是推荐连续自增的主键id&#xff0c;官方的推荐是auto_increment 一、准备三张表 分别是user_auto_key&#xff0c;user_uuid&#xff0c;user_random_key&#xff0c;分别表示自动增长的主键…

深度学习自然语言处理(NLP)模型BERT:从理论到Pytorch实战

文章目录 深度学习自然语言处理&#xff08;NLP&#xff09;模型BERT&#xff1a;从理论到Pytorch实战一、引言传统NLP技术概览规则和模式匹配基于统计的方法词嵌入和分布式表示循环神经网络&#xff08;RNN&#xff09;与长短时记忆网络&#xff08;LSTM&#xff09;Transform…