acwing1224. 交换瓶子

题目

题解

暴力

如果第i个位置不是a[i]的话，那么必然需要交换一次的，那么需要从第i+1个位置开始找到等于i的值进行交换

#include<iostream>
using namespace std;
const int N=10010;
int n,a[N];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int ans=0;
    for(int i=1;i<=n;i++){
        if(i!=a[i]){
            for(int j=i+1;j<=n;j++){
                if(a[j]==i){
                    swap(a[i],a[j]);
                    ans++;
                    break;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
    
}

方法二

#include<iostream>
using namespace std;
const int N=10010;
int n,a[N];
bool st[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int ans=0;
    for(int i=1;i<=n;i++){
        if(!st[i]){
            ans++;
            for(int j=i;!st[j];j=a[j]){
                   st[j]=true;
                
            }
        }
    }
    cout<<n-ans<<endl;
    return 0;
    
}