C++ 中使用给定单位的 a 和 b 可以遍历的最大元素数

给定一个二进制数组 **arr[]** 和两个变量 **a** 和 **b**，它们具有某些初始值。要遍历数组 **arr[]** 中的元素，有两种方法：

  • 如果 arr[i] == 1，则可以从 **a** 中使用 1 个单位，而 **b** 不变。如果从 **b** 中使用 1 个单位，则 **a** 增加 1 个单位。（注意，**a** 的值不能超过其原始值。）

  • 如果 arr[i] == 0，则可以从 **a** 或 **b** 中使用 1 个单位。

现在让我们用一个例子来理解我们必须做什么：

输入

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

输出

5

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

解释

要遍历第 1 个元素，请从 **a** 中使用 1 个单位 (a = 1, b = 2)。

要遍历第 2 个元素，请从 **a** 中使用 1 个单位 (a = 0, b = 2)。

要遍历第 3 个元素，请从 **b** 中使用 1 个单位 (a = 0, b = 1)。

要遍历第 4 个元素，请从 **b** 中使用 1 个单位，这会使 **a** 增加 1 个单位 (a = 1, b = 0)。

要遍历第 5 个元素，请从 **a** 中使用 1 个单位 (a = 0, b = 0)。

因此，我们遍历了所有元素，输出变为 5。

输入

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

输出

4

下面程序中使用的算法如下

  • 在函数 MaxElements() 中，初始化变量 **Oa** = 0 和 **max** = 0，它们都是 int 类型，分别用于存储 a 的原始值和最终答案。

  • 循环从 i = 0 到 i<size，检查数组中的每个元素。

  • 首先检查 **a** 和 **b** 是否都等于零，如果是，则退出循环。

  • 否则检查 (a == 0)，如果是，则检查当前元素是否等于 1，并从 b 中减去 1 以遍历该元素，并将 a 设置为 min(Oa, a + 1)，以便 a 不超过其原始值。

    否则，只需从 b 中减去 1 而不影响 a。

  • 否则检查 (b == 0)，如果是，则只需从 a 中减去 1。

  • 否则检查 (arr[i] == 1 && a < Oa)，如果是，则检查当前元素是否等于 1，并从 b 中减去 1 以遍历该元素，并将 a 设置为 min(Oa, a + 1)。

  • 否则，只需从 a 中减去 1 并增加 **max**。

  • 在循环外部，返回 **max**。

示例

实时演示

#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;
}

输出

4

更新于： 2020 年 8 月 4 日

56 次查看

开启你的 职业生涯

通过完成课程获得认证

开始
广告