[第七届蓝桥杯省赛C++B组]交换瓶子
C++ 蓝桥 交换 省赛 第七届
2023-09-11 14:18:49 时间
交换瓶子
来源: 第七届蓝桥杯省赛C++B组
算法标签 图论 环 置换群 贪心
题目描述
有 N 个瓶子,编号 1∼N,放在架子上。
比如有 5 个瓶子:
2 1 3 5 4
要求每次拿起 2 个瓶子,交换它们的位置。
经过若干次后,使得瓶子的序号为:
1 2 3 4 5
对于这么简单的情况,显然,至少需要交换 2 次就可以复位。
如果瓶子更多呢?你可以通过编程来解决。
输入格式
第一行包含一个整数 N,表示瓶子数量。
第二行包含 N 个整数,表示瓶子目前的排列状况。
输出格式
输出一个正整数,表示至少交换多少次,才能完成排序。
数据范围
1≤N≤10000,
输入样例1:
5
3 1 2 5 4
输出样例1:
3
输入样例2:
5
5 4 3 2 1
输出样例2:
2
思路
由样例1
3 1 2 5 4
转为
1 2 3 4 5
对于瓶子顺序而言 则会有
3 对应正确顺序的3的位子 即当前的 2
2 对应正确顺序的2的位子 即当前的 1
1 对应正确顺序的2的位子 即当前的 3
这连接则形成一个闭环
总共有两个闭环
环内两个点的变动可以使得环分裂为2
环外的两个点的变动可以使得两个环合并为1
环最简的情况下是 自指,即存在n个环
这种情况同时也是 该题转换为正确顺序之后的情况
则可以遍历出当前所有环的数量 k
从k变更到n 需要n-k步骤
答案即为 n-k
在实际的操作过程当中,遍历环可以从1(i)出发每次指向i=a[i]
即指向指定的目标
时间复杂度
实际从n^2优化到了n
C++ 代码
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e4+10;
bool st[N];
int a[N],n,k;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];//瓶子初始序号
for(int i=1;i<=n;i++)//从每个正确序号出发
if(!st[i])//如果没有走过
{
k++;//环数量加一
for(int j=i;!st[j];j=a[j])//走完这个环 每次变更指向a[j] 即瓶子初始序号的第j个
st[j]=true;
}
cout<<n-k;//环最简情况为自指 则最多有n个环 当前有k个环 从K达到n则需要n-k次
return 0;
}
相关文章
- java实现第二届蓝桥杯连通问题(C++)
- java实现第二届蓝桥杯地铁换乘(C++)
- java实现第二届蓝桥杯最小公倍数(c++)
- 第三届蓝桥杯C++B组国(决)赛真题
- 二分查找法的C++泛型实现
- 【思特奇杯·云上蓝桥-算法训练营】第十一届蓝桥杯大赛第二场省赛试题C&C++ 大学B组真题
- C/C++每日一练(20230410) 二叉树专场(4)
- Open3D(C++) 法线定向(2)——朝向相机位置
- c++模板学习06之类模板与函数模板区别
- 软考中级(软件设计师)——面向对象程序设计(C++&Java二选一的题15分-目标3分)
- 蓝桥杯官网 试题 PREV-94 历届真题 矩阵计数【第十届】【决赛】【研究生组】【C++】解法
- 蓝桥杯官网 试题 PREV-61 历届真题 装饰珠【第十一届】【决赛】【研究生组】【C++】【C】【Java】【Python】四种解法
- 蓝桥杯官网 试题 PREV-227 历届真题 回文日期【第十一届】【决赛】【研究生组】【C++】【C】【Java】【Python】四种解法
- 蓝桥杯官网 试题 PREV-230 历届真题 作物杂交【第十一届】【决赛】【研究生组】【C++】【C】【Java】【Python】四种解法
- 蓝桥杯官网 试题 PREV-251 历届真题 补给【第十一届】【决赛】【研究生组】【C++】【C】【Java】【Python】四种解法
- 蓝桥杯官网 试题 PREV-253 历届真题 质数行者【第十一届】【决赛】【研究生组】【C++】【Java】两种解法
- 蓝桥杯官网 试题 PREV-267 历届真题 异或数列【第十二届】【省赛】【研究生组】【C++】【Java】两种解法
- 蓝桥杯官网 试题 PREV-274 历届真题 分果果【第十二届】【省赛】【研究生组】【C++】【Java】两种解法
- 【华为OD机试 2023最新 】 士兵过河(C++)
- C++学习心得与c语言到c++衔接技巧
- C++中的struct也能定义类!!!
- c++获取当前时间
- C++ 图片格式转化和压缩
- C++ 编码优化 | 减少冗余拷贝或赋值
- C语言使用技巧(二十):万能模板【拿走不谢】:VS CODE配置C/C++编译环境
- 第十三届蓝桥杯C++B组国赛E题——出差 (AC)
- 学习C++:C++进阶(三)CMake基础篇---用一个小型项目了解CMake及环境构建