คำอธิบายปัญหา
กำหนดการเรียงลำดับของ N องค์ประกอบจาก 0 ถึง N-1 จุดคงที่ (fixed point) คือดัชนีที่ค่าของมันเท่ากับดัชนี คือ arr[i] = i คุณได้รับอนุญาตให้ทำการสลับ (swap) ได้สูงสุด 1 ครั้ง หาจำนวนจุดคงที่สูงสุดที่สามารถได้รับ
ตัวอย่าง
ถ้าอาร์เรย์นำเข้าคือ {0, 1, 2, 3, 4, 6, 5} คำตอบคือ 7
- เพื่อปรับจุดคงที่ เราต้องสลับ 6 และ 5
- หลังจากนี้ อาร์เรย์ทั้งหมดจะกลายเป็นจุดคงที่ และค่าสูงสุดของจุดคงที่คือ 7
อัลกอริทึม
- สร้างอาร์เรย์ pos ที่เก็บตำแหน่งของแต่ละองค์ประกอบในอาร์เรย์นำเข้า
- จากนั้น เราทำการเดินทางผ่านอาร์เรย์และมีกรณีดังต่อไปนี้:
- ถ้า a[i] = i เราสามารถเพิ่มจำนวนนับได้เลยและไปต่อ
- ถ้า pos[i] = a[i] ซึ่งหมายความว่าการสลับ 2 ตัวนี้จะทำให้ i และ a[i] กลายเป็นจุดคงที่ ทำให้จำนวนเพิ่มขึ้น 2 จำไว้ว่าสามารถสลับได้สูงสุด 1 ครั้งเท่านั้น
- ในตอนท้ายของการเดินทาง ถ้าเรายังไม่ได้ทำการสลับใดๆ แสดงว่าการสลับของเราไม่สามารถเพิ่มจำนวนนับได้ 2 ดังนั้น ถ้ามีองค์ประกอบอย่างน้อย 2 ตัวที่ไม่ใช่จุดคงที่ เราสามารถทำการสลับเพื่อเพิ่มจำนวนนับขึ้น 1 นั่นคือ ทำให้หนึ่งในจุดเหล่านั้นกลายเป็นจุดคงที่
ตัวอย่างโค้ด
#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; }ผลลัพธ์
เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้:
Maximum edges = 7
