Tìm hoán vị 2N số thỏa biểu thức giá trị tuyệt đối = 2K trong C++

Cho N, K (K ≤ N). Tìm hoán vị đầu tiên của 2N số tự nhiên thỏa:

∑|A_{2i-1} - A_{2i}| + |∑(A_{2i-1} - A_{2i})| = 2K

Ý tưởng: Xét dãy đã sắp xếp 1,2,3,4,... Hoán đổi cặp (2i-1, 2i) sẽ tăng kết quả đúng 2 đơn vị. Cần thực hiện K lần hoán đổi như vậy.

Ví dụ

#include <iostream>
using namespace std;

void showPermutations(int n, int k) {
    for (int i = 1; i <= n; i++) {
        int a = 2 * i - 1;
        int b = 2 * i;
        if (i <= k)
            cout << b << " " << a << " ";
        else
            cout << a << " " << b << " ";
    }
}

int main() {
    int n = 4, k = 2;
    showPermutations(n, k);
}

Kết quả

2 1 4 3 5 6 7 8