หาการเรียงสับเปลี่ยนของ 2N ตัวเลข ให้สมการค่าสัมบูรณ์ได้ 2K ใน C++

กำหนด N และ K หาการเรียงสับเปลี่ยน (Permutation) ของ 1, 2, ..., 2N ที่ทำให้สมการต่อไปนี้เป็นจริง:

$$\sum_{i=1}^N |A_{2i-1} - A_{2i}| - |\sum_{i=1}^N (A_{2i-1} - A_{2i})| = 2K$$

เงื่อนไข: K ≤ N

ตัวอย่าง: N=4, K=1 → Output: 2 1 3 4 (ค่าสมการ = 2)

แนวคิด

เริ่มจากลำดับเรียง 1, 2, 3, 4, 5, 6, ... หากสลับคู่ (2i-1, 2i) ค่าสมการจะเพิ่มขึ้นทีละ 2 ต้องทำการสลับ K คู่

ตัวอย่างโค้ด

#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);
    return 0;
}

ผลลัพธ์

2 1 4 3 5 6 7 8

การตรวจสอบ (N=4, K=2)

คู่: (2,1), (4,3), (5,6), (7,8)

ผลรวมค่าสัมบูรณ์: |2-1| + |4-3| + |5-6| + |7-8| = 1+1+1+1 = 4

ค่าสัมบูรณ์ของผลรวม: |(2-1)+(4-3)+(5-6)+(7-8)| = |1+1-1-1| = 0

ผลต่าง: 4 - 0 = 4 = 2K ✓