จำนวนองค์ประกอบสูงสุดที่ทำให้เท่ากันได้ด้วยการอัปเดต k ครั้งใน C++

ภารกิจคือการหาจำนวนองค์ประกอบสูงสุดที่สามารถทำให้เท่ากันได้ในอาร์เรย์ที่กำหนดหลังจากเพิ่มค่าขององค์ประกอบได้สูงสุด k ครั้ง

ตัวอย่าง

อินพุต

a[] = {1, 3, 8}, k = 4

เอาต์พุต

คำอธิบาย

ที่นี่เราสามารถได้ 2 ตัวเลข 4 โดยเพิ่ม 1 ไป 3 ครั้ง และเพิ่ม 3 ไป 1 ครั้ง ทำให้ a[] = {4, 4, 8}

อินพุต

arr = {2, 5, 9}, k = 2

เอาต์พุต

แนวทางที่ใช้ในโปรแกรมด้านล่าง

ใน main() เริ่มต้น int a[], size และ k เพื่อเก็บองค์ประกอบอาร์เรย์ ขนาดอาร์เรย์ และจำนวนการอัปเดตสูงสุด
ในฟังก์ชัน max() เริ่มต้นด้วยการจัดเรียงอาร์เรย์แบบเพิ่มขึ้น แล้วประกาศอาร์เรย์เพิ่ม 2 ตัว int p[size + 1] และ m[size + 1] ที่จะเก็บ prefix sum และค่าสูงสุดตามลำดับ
ลูป i = 0 ถึง i <= size เริ่มต้น p[i] = 0 และ m[i] = 0
นอกลูป กำหนด m[0] = arr[0] และ p[0] = arr[0]
ลูป i = 1 ถึง i < size คำนวณ p[i] = p[i - 1] + arr[i] สำหรับ prefix sum และ m[i] = max(m[i - 1], arr[i]) สำหรับค่าสูงสุดจนถึงตำแหน่งนั้น
หลังลูป เริ่มต้น int Lt = 1, Rt = size, result สำหรับค่าซ้าย ขวา และคำตอบสุดท้าย เริ่มต้น Binary Search
While loop เงื่อนไข (Lt < Rt) ภายใน mid = (Lt + Rt) / 2 ตรวจสอบ EleCal(p, m, mid - 1, k, size) ถ้าใช่ result = mid, Lt = mid + 1 มิฉะนั้น Rt = mid - 1
นอกลูป พิมพ์ result
ในฟังก์ชัน bool EleCal() เริ่มต้น for loop เงื่อนไข for (int i = 0, j = x; j <= size; j++, i++) ภายในตรวจสอบ if (x * m[j] - (p[j] - p[i]) <= k) ถ้าใช่ return true นอกลูป return false

ตัวอย่างโปรแกรม

#include <bits/stdc++.h>
using namespace std;

bool EleCal(int p[], int m[], int x, int k, int size) {
    for (int i = 0, j = x; j <= size; j++, i++) {
        if (x * m[j] - (p[j] - p[i]) <= k)
            return true;
    }
    return false;
}

void Max(int arr[], int size, int k) {
    sort(arr, arr + size);
    int p[size + 1];
    int m[size + 1];
    for (int i = 0; i <= size; ++i) {
        p[i] = 0;
        m[i] = 0;
    }
    m[0] = arr[0];
    p[0] = arr[0];
    for (int i = 1; i < size; i++) {
        p[i] = p[i - 1] + arr[i];
        m[i] = max(m[i - 1], arr[i]);
    }
    int Lt = 1, Rt = size, result;
    while (Lt < Rt) {
        int mid = (Lt + Rt) / 2;
        if (EleCal(p, m, mid - 1, k, size)) {
            result = mid;
            Lt = mid + 1;
        } else
            Rt = mid - 1;
    }
    cout << result;
}

int main() {
    int a[] = { 1, 3, 8 };
    int size = sizeof(a) / sizeof(a[0]);
    int k = 4;
    Max(a, size, k);
    return 0;
}