หาจำนวนการดำเนินการน้อยที่สุดเพื่อทำให้อาร์เรย์สวยงามใน C++

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

ได้รับอาร์เรย์ไบนารี bin[] ขนาด n ที่ประกอบด้วย 0 และ 1 เท่านั้น ต้องการหา จำนวนการดำเนินการน้อยที่สุด เพื่อทำให้อาร์เรย์กลายเป็น "อาร์เรย์สวยงาม" (Beautiful Array)

อาร์เรย์สวยงาม คือ อาร์เรย์ไบนารีที่มีรูปแบบสลับกันระหว่าง 0 และ 1 (เช่น 0,1,0,1... หรือ 1,0,1,0...)

ขั้นตอนการดำเนินการหนึ่งครั้ง ประกอบด้วย:

1. ขั้นตอน 1: ตัดอาร์เรย์ออกเป็นสองครึ่ง
2. ขั้นตอน 2: กลับลำดับ (reverse) ส่วนหนึ่งในสองครึ่ง
3. ขั้นตอน 3: นำสองครึ่งมาต่อกันอีกครั้ง

ตัวอย่าง

Input: bin[] = {1, 0, 1, 0, 0, 1}

Output: 1

คำอธิบาย: ตัดอาร์เรย์ สร้างซับอาร์เรย์ bin[4, 5] กลับลำดับแล้วนำมาต่อกลับเข้าไป

แนวทางแก้ปัญหา

โจทย์นี้สามารถลดรูปได้เป็นการหา จำนวนศูนย์ (0) ที่ติดกันมากที่สุด ซึ่งเท่ากับจำนวนการดำเนินการที่ต้องทำ

กรณีฐาน (Base Cases):

• ถ้าขนาดอาร์เรย์เป็น 1 → เป็นอาร์เรย์สวยงามอยู่แล้ว คืนค่า 0
• ถ้าขนาดอาร์เรย์เป็นเลขคี่ → ไม่สามารถเป็นอาร์เรย์สวยงามได้ คืนค่า -1

สำหรับขนาดคู่ ให้ตรวจสอบจำนวนศูนย์ติดกัน (consecutive zeros) ซึ่งจะเป็นจำนวนการดำเนินการ

อัลกอริทึม

1. เริ่มต้น zeroCount, oneCount, consZero = 0
2. ถ้า n == 1 คืนค่า 0
3. ถ้า n % 2 != 0 คืนค่า -1
4. ลูป i = 0 ถึง n-1:
   • ถ้า bin[i] == bin[i+1] == 0 ให้ consZero++
5. ตรวจสอบแบบวนรอบ: ถ้า bin[n-1] == bin[0] == 0 ให้ consZero++
6. คืนค่า consZero

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

#include <iostream>
using namespace std;

int minOperations(int bin[], int n) {
    if (n == 1) return 0;
    if (n % 2 != 0) return -1;
    
    int consZero = 0;
    for (int i = 0; i < n; ++i) {
        if (i + 1 < n) {
            if (bin[i] == 0 && bin[i + 1] == 0)
                consZero++;
        }
    }
    if (bin[0] == bin[n - 1] && bin[0] == 0)
        consZero++;
    
    return consZero;
}

int main() {
    int bin[] = { 1, 0, 1, 0, 0, 1 };
    int n = sizeof(bin) / sizeof(bin[0]);
    cout << "The minimum operations needed to make an Array beautiful is " << minOperations(bin, n);
    return 0;
}

ผลลัพธ์

The minimum operations needed to make an Array beautiful is 1