Đề bài
Cho một mảng kích thước N và mỗi phần tử là 1 hoặc 0. Nhiệm vụ là tính số phép toán tối thiểu cần thực hiện để chuyển đổi tất cả các phần tử thành 0. Có thể thực hiện các phép toán sau:
Nếu một phần tử là 1, bạn có thể thay đổi giá trị của nó thành 0 thì:
- Nếu phần tử tiếp theo liên tiếp là 1, nó sẽ tự động chuyển thành 0.
- Nếu phần tử tiếp theo liên tiếp đã là 0, thì không có gì xảy ra.
Nếu arr[] = {1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1} thì cần 4 phép toán để biến tất cả phần tử thành 0
Thuật toán
1. Nếu phần tử hiện tại là 1 thì tăng bộ đếm và tìm 0 tiếp theo vì tất cả các 1 liên tiếp sẽ tự động chuyển thành 0. 2. Trả về bộ đếm cuối cùng
Ví dụ
#include <iostream> #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) using namespace std; int performMinOperation(int *arr, int n){ int i, cnt = 0; for (i = 0; i < n; ++i) { if (arr[i] == 1) { int j; for (j = i + 1; j < n; ++j) { if (arr[j] == 0) { break; } } i = j - 1; ++cnt; } } return cnt; } int main(){ int arr[] = {1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1}; cout << "Minimum required operations = " << performMinOperation(arr, SIZE(arr)) << endl; return 0; }
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Minimum required operations = 4