คำชี้แจงปัญหา
ให้การเปลี่ยนแปลงขององค์ประกอบ N จาก 0 ถึง N-1 จุดคงที่คือดัชนีที่มีค่าเท่ากับดัชนีเช่น arr[i] =i คุณสามารถทำการแลกเปลี่ยนได้มากที่สุด 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 อัน โปรดทราบว่าการสลับสามารถทำได้สูงสุดครั้งเดียว .
- เมื่อสิ้นสุดการข้ามผ่าน หากเราไม่ได้ทำการสลับใดๆ หมายความว่าการแลกเปลี่ยนของเราไม่สามารถเพิ่มจำนวนขึ้น 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
