P1698 题解

ikunTLE · 2024-08-14 18:34:20 · 题解

题目传送门

思路

令 b 为排序后的 a。分为 2 种情况：

• 若 a_i=b_i，那么无需交换。
• 若 a_i\neq b_i，则需要将正确答案交换到 i 的位置上，即多了一次交换。

由于最后一个数交换后会回到正确的位置，所以答案需要 -1。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=105;
int a[N],b[N];
int main(){
    int n=read();
    for(int i=1;i<=n;++i)
        a[i]=b[i]=read();
    sort(b+1,b+n+1);
    int ans=-1;
    for(int i=1;i<=n;++i)
        ans+=(a[i]!=b[i]);
    printf("%d\n",ans);
    return 0;
}