Computer >> Máy Tính >  >> Lập trình >> C ++

Các phần tử tối đa có thể được gạch chéo bằng cách sử dụng các đơn vị a và b đã cho trong C ++

Cho một mảng nhị phân arr [] và hai biến a 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 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