ในบทช่วยสอนนี้ เราจะเขียนโปรแกรมที่หาการเปลี่ยนแปลงครั้งใหญ่ที่สุดหลังจากที่มีการแลกเปลี่ยนมากที่สุด k ครั้ง
มาดูขั้นตอนการแก้ปัญหากัน
- เริ่มต้นอาร์เรย์
- เริ่มต้นอาร์เรย์เพื่อจัดเก็บดัชนีด้วยขนาด n + 1
- วนซ้ำในอาร์เรย์และเก็บดัชนีของแต่ละองค์ประกอบไว้ในอาร์เรย์ตำแหน่ง
- เขียนลูปที่วนซ้ำจนถึง n และ k มากกว่า 0
- จัดเก็บตำแหน่งขององค์ประกอบ n - i ในตัวแปร temp
- อัปเดตตำแหน่งขององค์ประกอบปัจจุบัน arr[i] ด้วยตำแหน่ง[n - i].
- อัปเดตตำแหน่งตำแหน่ง[n - i] ด้วยดัชนีปัจจุบัน i.
- สลับองค์ประกอบปัจจุบัน arr[i] กับ arr[temp.Decrement k.
- พิมพ์องค์ประกอบอาร์เรย์
ตัวอย่าง
มาดูโค้ดกันเลย
#include <bits/stdc++.h>
using namespace std;
void getLargestPermutation(int arr[], int n, int k) {
int position[n + 1];
for (int i = 0; i < n; ++i) {
position[arr[i]] = i;
}
for (int i = 0; i < n && k; ++i) {
if (arr[i] == n - i) {
continue;
}
int temp = position[n - i];
position[arr[i]] = position[n - i];
position[n - i] = i;
swap(arr[temp], arr[i]);
--k;
}
}
int main() {
int arr[] = { 5, 3, 2, 6, 7, 1, 4 };
int n = 7, k = 3;
getLargestPermutation(arr, n, k);
for (int i = 0; i < n; ++i) {
cout << arr[i];
}
cout << endl;
return 0;
} ผลลัพธ์
หากคุณเรียกใช้โค้ดด้านบน คุณจะได้ผลลัพธ์ดังต่อไปนี้
7653214
บทสรุป
หากคุณมีข้อสงสัยใดๆ ในบทแนะนำ โปรดระบุในส่วนความคิดเห็น
