题解归档 - cf220A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf220A
• 本地来源：problems/cf220A/idea.md
• 题目链接：https://codeforces.com/contest/220/problem/A
• 原始标题：cf220A — Little Elephant and Problem

思路

cf220A — Little Elephant and Problem

题意

给定长度为 $n$ 的数组 $a$，判断是否能在 至多一次交换（0 次或 1 次，交换任意两个位置）内将其排成非降序。

做法

1. 复制 $a$ 得到 $b$，对 $b$ 排序。
2. 统计 $a_i \neq b_i$ 的下标个数 cnt，并记录前两个错位下标 p1, p2。

3. 判定：

   • cnt == 0：已排序 → YES
   • cnt == 2 且 a[p1]==b[p2] 且 a[p2]==b[p1]：交换这两处即可 → YES
   • 其余（cnt==1 或 cnt>=3）→ NO

正确性：一次交换只会改变两个位置的值；若排序后恰有两处不同，则必然就是应交换的那一对；0 处说明无需操作；其余情况一次交换不够。

复杂度

• 时间 $O(n \log n)$，空间 $O(n)$。

样例

验证

• 对拍 brute（枚举 0/1 次交换）500 组随机小数据（WSL/Kali 不可用时用 Python 逻辑对拍 2000 组）。
• 官方样例通过。

代码

来源：problems/cf220A/solution.cpp

/* Author: likely
 * Time: 2026-06-08 05:03:57
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005;
ll a[maxn+5],b[maxn+5],n,i,j,k,zc,pd,cur,dq,cnt,ans,p1,p2;
int main(){
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    cnt=0,p1=p2=0;
    for(i=1;i<=n;i++){
        if(a[i]!=b[i]){
            cnt++;
            if(cnt==1) p1=i;
            else p2=i;
        }
    }
    if(cnt==0) cout<<"YES\n";
    else if(cnt==2 and a[p1]==b[p2] and a[p2]==b[p1]) cout<<"YES\n";
    else cout<<"NO\n";
    return 0;
}