Beautiful Array ใน C++

คำอธิบายปัญหา

อาร์เรย์ A เรียกว่า beautiful หากเป็น permutation ของ 1..N และสำหรับทุก i < j ไม่มี k ที่ i < k < j ทำให้ A[k] * 2 = A[i] + A[j] (คือ ไม่มีค่ากึ่งกลางทางคณิตศาสตร์ระหว่างคู่ใดคู่หนึ่ง)

ตัวอย่าง: N=5 → [3,1,2,5,4] (อาจมีคำตอบหลายแบบ)

วิธีแก้ปัญหา (Divide and Conquer / Recursive Construction)

สร้างแบบ recursive: แยกเลขคี่และเลขคู่

1. เริ่มจาก [1]
2. ขยาย: odd = [2*x-1 for x in arr if 2*x-1 <= N]
3. even = [2*x for x in arr if 2*x <= N]
4. arr = odd + even
5. ทำซ้ำจนความยาว = 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] << (i+1 < v.size() ? ", " : "");
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> beautifulArray(int N) {
        vector<int> ret = {1};
        while(ret.size() < N) {
            vector<int> temp;
            for(int x : ret) {
                if(2*x - 1 <= N) temp.push_back(2*x - 1);
            }
            for(int x : ret) {
                if(2*x <= N) temp.push_back(2*x);
            }
            ret = temp;
        }
        return ret;
    }
};

int main() {
    Solution ob;
    print_vector(ob.beautifulArray(5));
    return 0;
}

อินพุต

5

เอาต์พุต

[1,5,3,2,4]