厦门营销型网站,电商网站设计公司力推亿企邦,建行24小时人工电话,WordPress评论第页题目 思路
可以交换任意两个瓶子#xff0c;最多n-1次#xff1b;如果是只能交换相邻的瓶子#xff0c;那么相当于逆序对的个数#xff08;这篇博客是介绍如何计算逆序对的算法#xff1a;算法篇#xff1a;逆序对_逆序对算法-CSDN博客#xff09;本题转换为图论去看:边…题目 思路
可以交换任意两个瓶子最多n-1次如果是只能交换相邻的瓶子那么相当于逆序对的个数这篇博客是介绍如何计算逆序对的算法算法篇逆序对_逆序对算法-CSDN博客本题转换为图论去看:边的连接规则:每个瓶子向它应该在的位置连一条边图的特点有n个点,n条边每个点的出度和入度为1初始是一堆环目标是变成五个自环情况一交换同一个环内的点必然会裂成两个环指向交换位置的箭头发生改变即被交换的数的入度来源发生变化情况二交换不同环中的点将两个环合并初始k个环目标是变成n个环最少n-k次就可以得解相当与转换求环的个数有多少
代码
n int(input())
b list(map(int, input().split()))
# 记录元素是否已被访问
st [False] * (n 1)cnt 0for i in range(0, n):# 如果当前元素尚未被访问if not st[i]:cnt 1# 从当前位置开始通过序列b跟踪下一个元素直到回到已访问过的元素或者到达末尾j iwhile not st[j]:# 标记当前位置已被访问st[j] True# 更新下一个要访问的位置j b[j-1] # 列表索引是从0开始需要调整为b[j-1]# j3应在的位置上是2即b[j-1]2# 输出未访问元素的数量
print(n - cnt)
