图论:根据题意,建立特殊图
抓住题意:
n个瓶子,把这个过程看成特殊环得交换出度方向得操作,从每一个点出发所建立的环的边数k,则结果即为n-k
时间复杂度:O(n)
#include<iostream>
using namespace std;
#define N 10010
int n,b[N];
bool st[N];
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i ++) scanf("%d",&b[i]);
int cnt = 0;
for(int i = 1;i <= n;i ++)
if(!st[i])
{
cnt ++;
for(int j = i; !st[j] ;j = b[j])
st[j] = true;
}
printf("%d\n",n - cnt);
return 0;
}
上面的想不到,那就没得说了,直接贪心
从头开始,DFS每个出发点,一直交换到不能再交换,看似两个for循环实际前面已经搞定了大部分,平均下来还是一样,总体来说比上一种方法慢一点
时间复杂度:O(n)
#include<iostream>
using namespace std;
#define N 10010
int n,b[N];
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i ++) scanf("%d",&b[i]);
int cnt = 0;
for(int i = 1;i <= n;i ++)
for(int j = i;j != b[j];j = b[j])
{
swap(b[j],b[b[j]]);
cnt ++;
}
printf("%d\n",cnt);
return 0;
}