Cho một mảng nhị phân arr [] và hai biến a và b với một số giá trị ban đầu. Để vượt qua một phần tử trong mảng arr [] có hai cách -
-
Nếu arr [i] ==1, thì 1 đơn vị có thể được sử dụng từ a , không có thay đổi về b . Nếu 1 đơn vị được sử dụng từ b , sau đó a tăng lên 1 đơn vị. (Lưu ý rằng giá trị của a không thể tăng lên trên giá trị ban đầu của nó.)
-
Nếu arr [i] ==0, thì 1 đơn vị có thể được sử dụng từ a hoặc b .
Bây giờ chúng ta hãy hiểu những gì chúng ta phải làm bằng cách sử dụng một ví dụ -
Đầu vào
arr[] = {0, 0, 0, 1, 1}, a = 2, b = 2
Đầu ra
5
Giải thích
Để vượt qua 1 st , sử dụng 1 đơn vị từ a (a =1, b =2).
Để vượt qua 2 nd , sử dụng 1 đơn vị từ a (a =0, b =2).
Để vượt qua thứ 3 , sử dụng 1 đơn vị từ b (a =0, b =1).
Để vượt qua thứ 4 , sử dụng 1 đơn vị từ b làm tăng a bằng 1 đơn vị (a =1, b =0).
Để vượt qua thứ 5 , sử dụng 1 đơn vị từ a (a =0, b =0).
Do đó, chúng tôi đã vượt qua tất cả các yếu tố và đầu ra trở thành 5.
Đầu vào
arr[] = {1, 1, 1, 0, 1}, a = 1, b = 2
Đầu ra
4
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Trong hàm MaxElements () khởi tạo các biến Oa =0 và tối đa =0, cả hai kiểu int để lưu trữ giá trị ban đầu của a và câu trả lời cuối cùng tương ứng.
-
Lặp lại từ i =0 đến i
-
Trước tiên, Kiểm tra xem cả hai a và b bằng 0, sau đó thoát ra khỏi vòng lặp.
-
Nếu không, hãy kiểm tra xem (a ==0) và nếu có, sau đó kiểm tra xem phần tử hiện tại =1 và trừ 1 từ b để vượt qua phần tử đó và đặt a =min (Oa, a + 1) để a không vượt quá ban đầu giá trị.
Khác chỉ cần trừ 1 cho b mà không ảnh hưởng đến a.
-
Nếu không, hãy kiểm tra xem (b ==0) và nếu có, sau đó chỉ cần trừ 1 cho a.
-
Nếu không, hãy kiểm tra xem (arr [i] ==1 &&a
-
Nếu không, chỉ cần trừ 1 từ a và tăng tối đa .
-
Bên ngoài vòng lặp, trả về max .
Ví dụ
#include <bits/stdc++.h> using namespace std; int MaxElements(int arr[], int a, int b, int size){ // Oa will have original value of a int Oa = a; int max = 0; // Iterate in the binary array for (int i = 0; i < size; i++){ // Break loop if a and b, both are = 0 if (a == 0 && b == 0) break; // If a is not present, use b else if (a == 0){ //increase a by 1 if arr[i] == 1 if (arr[i] == 1){ b -= 1; //Checking if original value is not exceeded a = min(Oa, a + 1); } else b -= 1; } // If b is not present, use a else if (b == 0) a--; // if arr[i] == 1,use b else if (arr[i] == 1 && a < Oa){ b -= 1; a = min(Oa, a + 1); } else a--; max++; } return max; } //main function int main(){ int arr[] = { 1, 1, 1, 0, 1 }; int size = sizeof(arr) / sizeof(arr[0]); int a = 1; int b = 2; cout << MaxElements(arr, a, b, size); return 0; }
Đầu ra
4