เราได้รับอาเรย์ 0 และ 1 แทนสถานะหลอดไฟที่ต่อสายเดียวกัน 0 = ปิด, 1 = เปิด สำหรับลำดับ N หลอด หากกดสวิตช์หลอด i ทุกหลอดทางขวา (i+1 ถึง n) จะสลับสถานะ (ON→OFF, OFF→ON) เป้าหมายคือหาจำนวนสวิตช์น้อยที่สุดที่ต้องกดเพื่อทำให้หลอดทุกดวงเปิด (1) สวิตช์เดียวกันกดได้หลายครั้ง เทียบเท่ากับการ flip สถานะทางขวาในอาเรย์ให้กลายเป็น 1 ทั้งหมด
อินพุต
Bulbs[] = {1, 0, 1, 0}
เอาต์พุต
Minimum right flips: 3
คำอธิบาย − สถานะเดิม 1010
กดสวิตช์ 2: 1 101 flip=1 กดสวิตช์ 3: 11 10 flip=2 กดสวิตช์ 4: 111 1 flip=3
อินพุต
Bulbs[] = {1, 0, 0, 0}
เอาต์พุต
Minimum right flips: 1
คำอธิบาย − กดสวิตช์ 2: 1 111 flip=1 ทุกหลอดทางขวาเปิด
วิธีการที่ใช้ในโปรแกรมด้านล่าง
- อาเรย์ arr[] เก็บสถานะหลอด
- ฟังก์ชัน minFlips(int arr[], int n) คืนค่าจำนวน right flips น้อยที่สุด
- count นับ flips, swich[] เก็บสถานะสวิตช์ (เริ่มต้น 0 ทุกตัว)
- ลูป i=0..n-1:
- ถ้า arr[i]==1 และ swich[i]==0 → ไม่ทำอะไร (i++)
- ถ้า arr[i]==0 และ swich[i]==1 → ไม่ทำอะไร (i++)
- ถ้า arr[i]==0 และ swich[i]==0 → count++ แล้ว flip สถานะทางขวา (while loop)
- คืนค่า count
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int minFlips(int arr[], int n) {
int count = 0;
int swich[n] = {0};
for (int i = 0; i < n; i++) {
if (arr[i] == 1 && swich[i] == 0) i++;
if (arr[i] == 0 && swich[i] == 1) i++;
if (arr[i] == 0 && swich[i] == 0) {
count++;
int j = i;
while (j < n) {
if (arr[j] == 0) arr[j++] = 1;
else arr[j++] = 0;
}
}
}
return count;
}
int main() {
int Arr[] = {0, 1, 0, 1};
int N = 4;
cout << "Minimum right flips to set all values in an array: " << minFlips(Arr, N);
return 0;
}
ผลลัพธ์
Minimum right flips to set all values in an array: 4
