รับอาร์เรย์ไบนารี arr[] และสองตัวแปร a และ ข ด้วยค่าเริ่มต้นบางอย่าง การข้ามองค์ประกอบในอาร์เรย์ arr[] มีสองวิธี -
-
ถ้า arr[i] ==1 ก็ใช้ได้ 1 หน่วยจาก a โดยไม่มีการเปลี่ยนแปลงใน b . หากใช้ 1 หน่วยจาก b แล้วเพิ่มขึ้น 1 หน่วย (โปรดทราบว่าค่าของ a ไม่สามารถเพิ่มให้สูงกว่าค่าเดิมได้)
-
ถ้า arr[i] ==0 จะใช้ได้ 1 หน่วยจาก a หรือ ข .
ตอนนี้มาทำความเข้าใจสิ่งที่เราต้องทำโดยใช้ตัวอย่าง -
อินพุต
arr[] = {0, 0, 0, 1, 1}, a = 2, b = 2 ผลลัพธ์
5
คำอธิบาย
เพื่อข้าม 1 st องค์ประกอบ ใช้ 1 หน่วยจาก a (a =1, b =2).
ที่จะข้าม 2 nd องค์ประกอบ ใช้ 1 หน่วยจาก a (a =0, b =2).
ที่จะข้าม 3 rd องค์ประกอบ ใช้ 1 หน่วยจาก b (a =0, b =1).
ที่จะข้าม 4 th องค์ประกอบ ใช้ 1 หน่วยจาก b ซึ่งเพิ่ม a โดย 1 หน่วย (a =1, b =0).
เพื่อข้าม 5 th องค์ประกอบ ใช้ 1 หน่วยจาก a (a =0, b =0).
ดังนั้นเราจึงข้ามองค์ประกอบทั้งหมดและผลลัพธ์กลายเป็น 5
อินพุต
arr[] = {1, 1, 1, 0, 1}, a = 1, b = 2 ผลลัพธ์
4
แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้
-
ในฟังก์ชัน MaxElements() เริ่มต้นตัวแปร Oa =0 และ สูงสุด =0 ทั้งสองชนิด int เพื่อเก็บค่าเดิมของ a และคำตอบสุดท้ายตามลำดับ
-
วนจาก i =0 จนถึง i
-
ตรวจสอบก่อนว่าทั้ง a และข มีค่าเท่ากับศูนย์แล้วจึงแยกออกจากลูป
-
อย่างอื่นตรวจสอบว่า (a ==0) และถ้าเป็นเช่นนั้นให้ตรวจสอบว่าองค์ประกอบปัจจุบัน =1 และลบ 1 จาก b เพื่อข้ามองค์ประกอบนั้นและใส่ a =min(Oa, a + 1) เพื่อให้ a ไม่เกินค่าเดิม ค่า.
อย่างอื่นเพียงแค่ลบ 1 จาก b โดยไม่กระทบต่อ a.
-
ให้ตรวจสอบว่า (b ==0) หรือไม่ ถ้าใช่ ก็ลบ 1 ออกจาก a
-
ตรวจสอบอย่างอื่นว่า (arr[i] ==1 &&a
-
อย่างอื่นเพียงแค่ลบ 1 จาก a และเพิ่ม สูงสุด .
-
นอกลูป ให้คืนค่า สูงสุด .
ตัวอย่าง
#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
