Sắp xếp đẹp II (Beautiful Arrangement II) trong C++

Cho hai số nguyên n và k, xây dựng mảng chứa các số từ 1 đến n sao cho mảng hiệu tuyệt đối giữa các phần tử liền kề có đúng k giá trị khác nhau.

Ví dụ: n=3, k=2 → [1,3,2] (hiệu: [2,1] có 2 giá trị riêng biệt).

Thuật toán

1. Dùng hai con trỏ i=1, j=n.
2. Khi 1:
   • Nếu k lẻ → thêm i, tăng i.
   • Nếu k chẵn → thêm j, giảm j.
   • Giảm k.
3. Khi , thêm các số còn lại theo thứ tự tăng dần từ i.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int> ret;
        for (int i = 1, j = n; i <= j; ) {
            if (k > 1) {
                ret.push_back(k % 2 ? i : j);
                if (k % 2 == 1) i++; else j--;
                k--;
            } else {
                ret.push_back(i++);
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    print_vector(ob.constructArray(3, 2));
    return 0;
}

Đầu vào / Đầu ra

Input: 3 2

Output: [1, 3, 2] (hoặc [3, 1, 2] tùy triển khai)