สมมติว่าเรามีตัวเลขสองตัว n และ k เราต้องสร้างการเรียงสับเปลี่ยน A โดยใช้ตัวเลข 1 ถึง n ซึ่งมีจุดยอด (peaks) ทั้งหมด k จุด ดัชนี i ถูกกล่าวว่าเป็นยอดของอาร์เรย์ A ถ้า A[i] > A[i-1] และ A[i] > A[i+1] หากทำไม่ได้ ให้คืนค่า -1
เช่น ถ้าค่าที่ป้อนเข้าเป็น n = 5; k = 2 ผลลัพธ์จะได้ [2, 4, 1, 5, 3] คำตอบอื่นก็ได้
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
ถ้า k > (n - 1) / 2 แล้ว: คืนค่า -1 กำหนดอาร์เรย์ a ขนาด: 101. สำหรับ i := 1 เมื่อ i <= n เพิ่ม i ทีละ 1 ทำ: a[i] := i สำหรับ i := 2 เมื่อ i <= 2 * k เพิ่ม i := i + 2 ทำ: สลับ a[i] และ a[i + 1] สำหรับ i := 1 เมื่อ i <= n เพิ่ม i ทีละ 1 ทำ: พิมพ์ a[i]
ตัวอย่างโค้ด
ดูการนำไปใช้จริงด้านล่างเพื่อความเข้าใจที่ดียิ่งขึ้น:
#include <bits/stdc++.h> using namespace std; void solve(int n, int k) { if (k > (n - 1) / 2) { cout << "-1"; return; } int a[101]; for (int i = 1; i <= n; i++) a[i] = i; for (int i = 2; i <= 2 * k; i += 2) { swap(a[i], a[i + 1]); } for (int i = 1; i <= n; i++) cout << a[i] << ", "; } int main() { int n = 5; int k = 2; solve(n, k); }
ข้อมูลนำเข้า
5, 2
ข้อมูลส่งออก
1, 3, 2, 5, 4,
