ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n และตัวเลข S หน้าที่ของเราคือ ค้นหาค่าสูงสุดที่เป็นไปได้ของค่าต่ำสุดของอาร์เรย์ที่แก้ไข .
นี่คือกฎในการแก้ไขอาร์เรย์
-
ความแตกต่างระหว่างผลรวมขององค์ประกอบอาร์เรย์ก่อนและหลังการแก้ไขควรเป็น S
-
ไม่อนุญาตให้ใช้ค่าลบในอาร์เรย์ที่แก้ไข
-
หากอาร์เรย์ที่แก้ไข ค่าต่ำสุดของอาร์เรย์ต้องขยายให้ใหญ่สุด
-
การปรับเปลี่ยนอาร์เรย์สามารถทำได้โดย เพิ่มหรือลดองค์ประกอบใดๆ ของอาร์เรย์ .
เมื่อใช้ข้อจำกัดเหล่านี้ เราจำเป็นต้องค้นหาอาร์เรย์ใหม่และคืนค่าสูงสุดสำหรับองค์ประกอบที่เล็กที่สุดของอาร์เรย์
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input : arr[] = {4, 5, 6} S = 2
Output : 4 คำอธิบาย
อาร์เรย์ที่แก้ไขคือ $4, 5, 5}
แนวทางการแก้ปัญหา
เราจำเป็นต้องเพิ่มค่าที่น้อยที่สุดของอาร์เรย์ที่แก้ไขให้มากที่สุด เราจะดำเนินการนี้โดยใช้การค้นหาไบนารีของค่าที่เหมาะสมที่สุดสำหรับค่าที่น้อยที่สุดซึ่งอยู่ระหว่าง 0 (น้อยที่สุด) และ arrนาที (มากที่สุดเท่าที่จะเป็นไปได้). เราจะตรวจสอบส่วนต่างเพื่อหาค่าที่น้อยที่สุดที่เป็นไปได้
เงื่อนไขพิเศษบางส่วน
ถ้า S มากกว่าผลรวมอาร์เรย์ จะไม่มีทางแก้ไขได้
ถ้า S เท่ากับผลรวมอาร์เรย์ 0 จะเป็นค่าขององค์ประกอบขั้นต่ำ
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
int findmaximisedMin(int a[], int n, int S){
int minVal = a[0];
int arrSum = a[0];
for (int i = 1; i < n; i++) {
arrSum += a[i];
minVal = min(a[i], minVal);
}
if (arrSum < S)
return -1;
if (arrSum == S)
return 0;
int s = 0;
int e = minVal;
int ans;
while (s <= e) {
int mid = (s + e) / 2;
if (arrSum - (mid * n) >= S) {
ans = mid;
s = mid + 1;
}
else
e = mid - 1;
}
return ans;
}
int main(){
int a[] = { 4, 5, 6 };
int S = 2;
int n = sizeof(a) / sizeof(a[0]);
cout<<"The maximum value of minimum element of the modified array is "<<findmaximisedMin(a, n, S);
return 0;
} ผลลัพธ์
The maximum value of minimum element of the modified array is 4
