题目描述
blablabla
样例
blablabla
算法1
暴力+贪心
对于一个位置和自身编号不同的瓶子,必然要进行一次交换才能将二者匹配,那么就可以从前往后枚举每一个瓶子,发现某一位置j与编号i不同,就再从该位置后开始搜,搜到放有编号为j的瓶子,然后将两个瓶子交换,使位置j成功匹配。因为每一次交换操作都是必须的,因此可以保证答案的正确性
时间复杂度 O(N^2)
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n;
int a[10001];
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int sum=0;
for(int i=1;i<=n;i++)
{
if(a[i]!=i)
{
for(int j=i+1;j<=n;j++)
{
if(a[j]==i)
{
swap(a[i],a[j]);
sum++;
break;
}
}
}
}
cout<<sum;
return 0;
}
算法2
图论+置换群
将瓶子编号与所在的位置编号对应的两个数字连一条边,易得每个数字均有且仅有一条入边和一条出边。那么整个图无分叉结构(入度初度大于了1),也不会形成链(存在入度初度为0的点),所以只会形成若干个环。交换后的状态是每一个数字都形成一个自环。两种状态的改变操作只有两类:
1.将位于不同环的两个数交换——环的数量会减少1
2.将位于相同环的两个数交换——环的数量会增加1
又因为每一次是任意交换两个瓶子,故若初始时形成了k个环,最终想要形成n个环,就必然可进行最少n-k步操作2,使环的数量逐渐增加到n。所以只需统计初始时环的数量k即可,ans==n-k
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n;
int a[10001];
bool st[10001];//st[i]==true表示点i已经在某个环中
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int sum=0;
for(int i=1;i<=n;i++)
{
if(!st[i])//开始形成环
{
sum++;
for(int j=i;!st[j];j=a[j])//使该环封闭
{
st[j]=true;
}
}
}
cout<<n-sum;
return 0;
}