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