Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Số phần tử tối đa có thể vượt qua dùng đơn vị a và b cho trước trong C++

Cho mảng nhị phân arr[] và hai biến a, b có giá trị ban đầu. Để vượt qua phần tử trong arr[] có hai cách:

  • Nếu arr[i] == 1: dùng 1 đơn vị từ a, b không đổi. Nếu dùng 1 đơn vị từ b, thì a tăng 1 đơn vị (lưu ý: a không được vượt quá giá trị ban đầu).
  • Nếu arr[i] == 0: dùng 1 đơn vị từ a hoặc b.

Ví dụ 1

Đầu vào** –

arr[] = {0, 0, 0, 1, 1}, a = 2, b = 2

Đầu ra** – 5

Giải thích** –

  • Phần tử 1: dùng a (a=1, b=2)
  • Phần tử 2: dùng a (a=0, b=2)
  • Phần tử 3: dùng b (a=0, b=1)
  • Phần tử 4: dùng b → a tăng 1 (a=1, b=0)
  • Phần tử 5: dùng a (a=0, b=0)

Vượt qua tất cả 5 phần tử.

Ví dụ 2

Đầu vào** –

arr[] = {1, 1, 1, 0, 1}, a = 1, b = 2

Đầu ra** – 4

Phương pháp trong chương trình

  • Hàm MaxElements(): khởi tạo Oa (giá trị gốc a) và max = 0.
  • Duyệt mảng: nếu a=b=0 thì dừng.
  • Nếu a=0: nếu arr[i]=1 thì dùng b, a = min(Oa, a+1); nếu arr[i]=0 thì dùng b.
  • Nếu b=0: dùng a.
  • Nếu arr[i]=1 và a < Oa: dùng b, a = min(Oa, a+1).
  • Ngược lại: dùng a.
  • Tăng max sau mỗi bước vượt qua.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int MaxElements(int arr[], int a, int b, int size) {
    int Oa = a;
    int max = 0;
    for (int i = 0; i < size; i++) {
        if (a == 0 && b == 0)
            break;
        else if (a == 0) {
            if (arr[i] == 1) {
                b -= 1;
                a = min(Oa, a + 1);
            } else
                b -= 1;
        } else if (b == 0)
            a--;
        else if (arr[i] == 1 && a < Oa) {
            b -= 1;
            a = min(Oa, a + 1);
        } else
            a--;
        max++;
    }
    return max;
}

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