ได้รับอาร์เรย์บाइनารี (0,1) ขนาดใดก็ได้ และค่า base หาจำนวน 1 น้อยที่สุดที่ "ให้พลัง" (lend power) ทำให้อาร์เรย์ทั้งหมดเป็น powerful 1 สามารถให้พลังกับตัวติดกันหรือภายในระยะ base ได้
ตัวอย่าง
Input: arr[] = {1,1,0,1,1,0,1}, base = 7
Output: Minimum 1s to lend power to make whole array powerful are: 1
คำอธิบาย: base=7 ≥ ขนาดอาร์เรย์ 1 ตัวแรกครอบคลุมทั้งหมด
Input: arr[] = {1,1,0,1,1,0,1}, base = 3
Output: Minimum 1s to lend power to make whole array powerful are: 2
คำอธิบาย: 1 ที่ index 2 ครอบคลุม 2 ตัวถัดไป, 1 ที่ index 5 ครอบคลุมต่อ → 2 ตัว
Input: arr[] = {1,1,0,1,1,0,1}, base = 1
Output: Impossible to make entire array powerful
คำอธิบาย: base=1 ให้พลังได้แค่ตัวเอง → ไม่สามารถครอบคลุม 0 ทั้งหมดได้
อัลกอริทึม: Greedy + Preprocessing
- สร้าง
arr_2[i]= index ของ 1 ล่าสุดก่อนหรือเท่ากับ i (prefix latest 1) - วน i = 0 ถึง size-1 แบบกระโดด:
reset_base = i + base - 1(ตำแหน่งไกลสุดที่ base ครอบคลุมจาก i)set = arr_2[min(reset_base, size-1)](1 ล่าสุดในช่วงที่ base ครอบคลุม)- ถ้า
set == -1หรือset + base <= i→ ไม่สามารถครอบคลุมได้ คืน -1 - กระโดดไป
i = set + baseเพิ่ม count
- คืน count
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
int Lend_Power(int arr[], int size, int base) {
int arr_2[size];
int temp = -1, count = 0;
for (int i = 0; i < size; i++) {
if (arr[i] == 1) temp = i;
arr_2[i] = temp;
}
for (int i = 0; i < size; ) {
int reset_base = i + base - 1;
int reset_size = size - 1;
int set = arr_2[min(reset_base, reset_size)];
if (set == -1 || set + base <= i) return -1;
i = set + base;
count++;
}
return count;
}
int main() {
int arr[] = {1, 1, 0, 1, 1, 0, 1};
int base = 2;
int size = sizeof(arr) / sizeof(arr[0]);
int val = Lend_Power(arr, size, base);
if (val == -1) cout << "Impossible to make entire array powerful";
else cout << "Minimum 1s to lend power to make whole array powerful are: " << val;
return 0;
}
ผลลัพธ์
Minimum 1s to lend power to make whole array powerful are: 3
