ZZU 月賽 E 題 Fixed Points 題解：最多一次交換最大化固定點數量

題目大意

給定長度 n (1 ≤ n ≤ 1e5) 的排列 a[0..n-1]（含 0 到 n-1 各一次）。固定點定義為 a[i] == i。允許最多交換一次任意兩個元素，求最大可能固定點數。

分析

• 初始固定點數 ans 直接統計。
• 一次交換最多增加 2 個固定點：若存在 i != j 使 a[i]=j 且 a[j]=i，交換後兩者均成固定點。條件等價於 a[a[i]] == i 且 a[i] != i。
• 若無法增加 2，但存在非固定點，交換任一非固定點與其目標位置可增加 1 個固定點。
• 若全為固定點，交換不增加（或減少），答案不變。

算法流程

1. 遍歷數組，統計 ans 並標記固定點 is[i]=1。
2. 再次遍歷非固定點 i，檢查 a[a[i]] == i，若真返回 ans+2。
3. 若步驟 2 失敗但存在非固定點，返回 ans+1。
4. 否則返回 ans。

AC 代碼 (C++)

#include <cstdio>
#include <cstring>
using namespace std;
int fun(int a[], int is[], int n) {
    int flag = 0;
    for (int i = 0; i < n; i++) {
        if (is[i] == 0) {
            if (i == a[a[i]]) return 2;
            flag++;
        }
    }
    if (flag) return 1;
    return 0;
}
int main() {
    int n, a[100010], is[100010];
    while (scanf("%d", &n) != EOF) {
        int ans = 0;
        memset(is, 0, sizeof(is));
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            if (a[i] == i) { is[i] = 1; ans++; }
        }
        printf("%d\n", ans + fun(a, is, n));
    }
    return 0;
}

複雜度

時間 O(n)，空間 O(n)，滿足 n=1e5 限制。