หาค่าสูงสุดที่เป็นไปได้ของค่าต่ำสุดของอาร์เรย์ที่ปรับเปลี่ยนแล้วใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n และตัวเลข S งานของเราคือ การหาค่าสูงสุดที่เป็นไปได้ของค่าต่ำสุดของอาร์เรย์ที่ปรับเปลี่ยนแล้ว

กฎในการปรับเปลี่ยนอาร์เรย์:

• ความต่างระหว่างผลรวมอาร์เรย์ก่อนและหลังปรับเปลี่ยนต้องเท่ากับ S
• ไม่允许ค่าติดลบในอาร์เรย์ที่ปรับเปลี่ยนแล้ว
• ในอาร์เรย์ที่ปรับเปลี่ยนแล้ว ค่าต่ำสุดต้องถูกเพิ่มให้มากที่สุด (maximize)
• การปรับเปลี่ยนสามารถทำได้โดย เพิ่มหรือลดค่าของสมาชิกในอาร์เรย์

ภายใต้เงื่อนไขเหล่านี้ เราต้องหาอาร์เรย์ใหม่และคืนค่าที่เพิ่มขึ้นแล้วของสมาชิกที่มีค่าน้อยที่สุด

ตัวอย่างเพื่อความเข้าใจ

Input : arr[] = {4, 5, 6} S = 2 
Output : 4

คำอธิบาย

อาร์เรย์ที่ปรับเปลี่ยนแล้วคือ {4, 5, 5}

แนวทางแก้ปัญหา

เราต้องเพิ่มค่าต่ำสุดของอาร์เรย์ที่ปรับเปลี่ยนแล้วให้มากที่สุด เราจะทำได้โดยใช้ Binary Search หาค่าที่เหมาะสมสำหรับค่าต่ำสุด ซึ่งอยู่ระหว่าง 0 (น้อยที่สุด) และ arr_min (มากที่สุด) เราจะตรวจสอบความต่างสำหรับค่าต่ำสุดที่เป็นไปได้

เงื่อนไขพิเศษ:

• หาก 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