Số điểm cố định tối đa sau tối đa 1 lần hoán đổi trong C++

Đề bài

Cho một hoán vị của N phần tử từ 0 đến N-1. Một điểm cố định là chỉ số i mà giá trị tại chỉ số đó bằng chính chỉ số đó: arr[i] = i. Bạn được phép thực hiện tối đa 1 lần hoán đổi. Tìm số điểm cố định lớn nhất có thể đạt được.

Ví dụ

Nếu mảng đầu vào là {0, 1, 2, 3, 4, 6, 5} thì kết quả là 7.

• Để điều chỉnh điểm cố định, hoán đổi 6 và 5
• Sau hoán đổi, toàn bộ mảng trở thành điểm cố định, giá trị lớn nhất là 7.

Thuật toán

1. Tạo mảng pos lưu vị trí của từng phần tử trong mảng đầu vào
2. Duyệt mảng và xử lý các trường hợp:
   • Nếu arr[i] == i: tăng bộ đếm và tiếp tục
   • Nếu pos[i] == arr[i] (hoán đổi 2 phần tử sẽ tạo ra 2 điểm cố định): tăng bộ đếm thêm 2, đánh dấu đã hoán đổi (chỉ cho phép 1 lần)
3. Sau duyệt: nếu chưa hoán đổi và còn ít nhất 2 phần tử không phải điểm cố định, có thể hoán đổi để tăng 1 điểm cố định

Chương trình C++

#include <bits/stdc++.h> 
using namespace std; 

int getMaximumFixedPoints(int arr[], int n) {
    int i, pos[n], count = 0, swapped = 0;
    for (i = 0; i < n; i++)
        pos[arr[i]] = i;
    
    for (i = 0; i < n; i++) {
        if (arr[i] == i) {
            count++;
        } else if (swapped == 0 && pos[i] == arr[i]) {
            count += 2;
            swapped = 1;
        }
    }
    
    if (swapped == 0 && count < n - 1) {
        count++;
    }
    return count;
}

int main() {
    int arr[] = {0, 1, 2, 3, 4, 6, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum value of fixed point = " << getMaximumFixedPoints(arr, n) << endl;
    return 0;
}

Kết quả

Maximum value of fixed point = 7