C++ में k अपडेट के साथ बराबर किए जा सकने वाले अधिकतम तत्व

दिया गया कार्य एक दी गई सरणी में अधिकतम तत्वों की संख्या ढूंढना है जिन्हें अधिकतम k बार इसके तत्वों को बढ़ाकर बराबर बनाया जा सकता है।

उदाहरण

इनपुट

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

आउटपुट

व्याख्या

यहां हम दो चार प्राप्त कर सकते हैं 1 को तीन बार बढ़ाकर और 3 को एक बार बढ़ाकर, जो a[] = {4, 4, 8} बनाता है।

इनपुट

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

आउटपुट

नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है

main() फ़ंक्शन में सरणी तत्वों, सरणी के आकार और अधिकतम अपडेट को क्रमशः संग्रहीत करने के लिए int a[], size और k आरंभ करें।
max() फ़ंक्शन में, पहले सरणी को आरोही क्रम में क्रमबद्ध करें और फिर दो और सरणी 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] रखें और उस स्थिति तक अधिकतम मान की गणना करने के लिए m[i] = max(m[i - 1], arr[i]) रखें।
लूप के बाद, बाइनरी खोज शुरू करने के लिए int Lt = 1, Rt = size, result आरंभ करें ताकि बाएं मान, दाएं मान और अंतिम उत्तर क्रमशः संग्रहीत हो सके।
शर्त (Lt < Rt) के साथ while लूप शुरू करें। लूप के अंदर int mid = (Lt + Rt) / 2 रखें। जांचें कि क्या (EleCal(p, m, mid - 1, k, size))। यदि हां, तो result = mid और Lt = mid + 1 रखें। अन्यथा बस Rt = mid - 1 रखें।
लूप के बाहर result प्रिंट करें।
bool EleCal() फ़ंक्शन में शर्त for (int i = 0, j = x; j <= size; j++, i++) के साथ for लूप शुरू करें।
लूप के अंदर जांचें कि क्या (x * m[j] - (p[j] - p[i]) <= k)। यदि हां, तो true वापस करें। लूप के बाहर 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;
}

// main फ़ंक्शन
int main(){
    int a[] = { 1, 3, 8 };
    int size = sizeof(a) / sizeof(a[0]);
    int k = 4;
    Max(a, size, k);
    return 0;
}