Chúng ta được cho một mảng 0 và 1 đại diện cho trạng thái bóng đèn nối cùng một dây theo trình tự. 0 đại diện cho bóng đèn TẮT và 1 đại diện cho bóng đèn BẬT. Với chuỗi N bóng đèn như vậy, nếu công tắc của bóng đèn được nhấn thì tất cả bóng đèn bên phải (i+1 đến n) thay đổi trạng thái trước, từ BẬT sang TẮT hoặc từ TẮT sang BẬT.
Với trạng thái đã cho của tất cả bóng đèn, mục tiêu là tìm số công tắc tối thiểu cần nhấn để bật tất cả chúng. [cùng một công tắc có thể nhấn nhiều lần]. Nó giống như lật trạng thái các giá trị chỉ số bên phải trong mảng để thiết lập tất cả thành 1.
Ví dụ
Đầu vào
Bulbs[] = { 1, 0, 1, 0 }
Đầu ra
Số lần lật phải tối thiểu: 3
Giải thích
Trạng thái gốc 1010
Nhấn công tắc 2: 1:101 count=1 Nhấn công tắc 3: 11:10 count=2 Nhấn công tắc 4: 111:1 count=3
Đầu vào
Bulbs[] = { 1, 0, 0, 0 }
Đầu ra
Số lần lật phải tối thiểu: 1
Giải thích
Trạng thái gốc 1000 Nhấn công tắc 2: 1:111 count=1 Tất cả bóng đèn bên phải bật.
Phương pháp sử dụng trong chương trình dưới đây
- Số nguyên lưu trạng thái N bóng đèn.
- Hàm minFlips(int arr[], int n) nhận mảng và độ dài n, trả về số lần lật phải tối thiểu để thiết lập giá trị mảng (bật tất cả bóng tắt).
- Biến count lưu số lần lật, khởi tạo 0.
- Mảng switch[] lưu trạng thái ban đầu của tất cả công tắc tương ứng bóng i. Tất cả 0 (switch[] = {0}).
- Bắt đầu từ i=0 đến n làm sau:
- Nếu bóng BẬT và công tắc tắt, không làm gì (tăng i).
- Nếu bóng TẮT và công tắc bật, không làm gì (tăng i) vì tắt công tắc không làm gì cho trạng thái bóng.
- Nếu bóng TẮT và công tắc tắt, tăng count và thay đổi trạng thái tất cả bóng bên phải (vòng while).
- Sau vòng for trả về kết quả trong 'count' là số lần lật.
- Trả về count.
Ví dụ mã nguồn
// C++ program to find minimum number of move-to-front
// moves to arrange items in sorted order.
#include <bits/stdc++.h>
using namespace std;
// Tính số lần di chuyển tối thiểu để sắp xếp mảng
// theo thứ tự tăng dần.
int minFlips(int arr[], int n) {
int count = 0;
int swich[n] = {0}; // Ban đầu không lật trạng thái, nên flip là false
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 << "Số lần lật phải tối thiểu thiết lập tất cả giá trị mảng: "
<< minFlips(Arr, N);
return 0;
}
Kết quả
Số lần lật phải tối thiểu thiết lập tất cả giá trị mảng: 4