题目描述
有 N 个瓶子,编号 1∼N,放在架子上。
比如有 5 个瓶子:
2 1 3 5 4
要求每次拿起 2 个瓶子,交换它们的位置。
经过若干次后,使得瓶子的序号为:
1 2 3 4 5
对于这么简单的情况,显然,至少需要交换 2 次就可以复位。
如果瓶子更多呢?你可以通过编程来解决。
数据范围
1≤N≤10000,
此题借助图形的分析,即可以将当前的位置信息用环表示,每个数应该指向这个数作为序号时对应的数
又根据定理:
1 交换同一个环中的两个点,这个环会变成两个环
2 交换两个环中的两个点,两个环会变成一个环
当所有的环中都只有一个数时,所有的瓶子都在对应的位置上了(形成自环)
由于题要求求最少次数,所以我们假设最好情况,每次交换的都是同一个环的数,即交换一次,环数加1,所以最小交换次数就是瓶子数减去,初始状态下环数
所以题目就变成如何求,初始状态下的环数。
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
using namespace std;
const int N=10010;
int b[N];
bool st[N];
int main()
{
int n;
cin>>n;
int i,j;
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
int cnt=0;
//寻找在题干给定状态下,存在多少个环
for(i=1;i<=n;i++)
{
if(!st[i])//如果当前点不在任何一个环中
{
cnt++;//一定存在一个包含当前点的环
for(j=i;!st[j];j=b[j])//找到和当前点在一个环里的所有点
st[j]=true;//修改这些点的状态
}
}
cout<<n-cnt<<endl;
}