Giả sử chúng ta có hai số n và k. Chúng ta phải xây dựng một hoán vị A sử dụng các số từ 1 đến n có đúng k đỉnh. Chỉ số i được gọi là đỉnh của mảng A, nếu A[i] > A[i-1] và A[i] > A[i+1]. Nếu không thể, trả về -1.
Ví dụ, nếu đầu vào là n = 5; k = 2, thì đầu ra sẽ là [2, 4, 1, 5, 3], các đáp án khác cũng có thể.
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
if k > (n - 1) / 2, thì: return -1 Định nghĩa mảng a kích thước: 101. for khởi tạo i := 1, khi i <= n, cập nhật (tăng i lên 1), do: a[i] := i for khởi tạo i := 2, khi i <= 2 * k, cập nhật i := i + 2, do: hoán đổi a[i] và a[i + 1] for khởi tạo i := 1, khi i <= n, cập nhật (tăng i lên 1), do: in a[i]
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#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); }Đầu vào
5, 2
Đầu ra
1, 3, 2, 5, 4,