C++ में अधिकतम K चालों में रेंज [L, R] में संख्याओं के योग को अधिकतम करें

हमें एक सरणी Arr[] दी गई है जिसमें पूर्णांक हैं और 2D सरणी Q जिसमें क्वेरीज़ हैं। प्रत्येक क्वेरी में 3 मान होते हैं: lpos, rpos और K। एक सूचकांक i से अगले सूचकांक i+1 पर एक चरण में जा सकता है या उसी सूचकांक पर रह सकता है। lpos से rpos तक अधिकतम K चरणों में जा सकते हैं। प्रत्येक चरण पर बाएं सबसे बाएं नंबर सहित सभी नंबरों को जोड़ें। लक्ष्य अधिकतम K चालों में योग को अधिकतम करना है। यदि lpos से rpos तक K चरणों में कोई गति संभव नहीं है तो "No" प्रिंट करें।

विभिन्न इनपुट-आउटपुट परिदृश्य देखते हैं:

इनपुट: Arr[] = {1, 2, 4, -1}; Q[][3] = { { 0, 2, 2 }, { 0, 2, 1 }, { 3, 3, 1 }, { 0, 2, 3} };

आउटपुट:

क्वेरी 1: 7

क्वेरी 2: NO

क्वेरी 3: NO

क्वेरी 4: 11

व्याख्या:

पहली क्वेरी:

हम सूचकांक 0 से 2 तक अधिकतम 2 चरणों में जा सकते हैं:

चरण 1: सूचकांक 0 से 1 (1+2=3)

चरण 2: सूचकांक 1 से 2 (3+4=7)

दूसरी क्वेरी:

हम सूचकांक 0 से 2 तक अधिकतम 1 चरण में नहीं जा सकते। "NO" प्रिंट करें।

तीसरी क्वेरी:

हम सूचकांक 3 से 3 तक अधिकतम 1 चरण में नहीं जा सकते। "NO" प्रिंट करें।

चौथी क्वेरी:

हम सूचकांक 0 से 2 तक अधिकतम 3 चरणों में जा सकते हैं:

चरण 1: सूचकांक 0 से 1 (1+2=3)

चरण 2: सूचकांक 1 से 2 (3+4=7)

चरण 3: सूचकांक 2 पर रहें (7+4=11)

इनपुट: Arr[] = { 1, 2, 3, 3, 2 }; Q[][3] = { { 0, 3, 2 }, { 1, 4, 3 } };

आउटपुट:

क्वेरी 1: NO

क्वेरी 2: 10

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

इस दृष्टिकोण में हम lpos से rpos की रेंज के लिए सेगमेंट ट्री का उपयोग करेंगे ताकि अधिकतम संभव मान ढूंढ सकें और प्रीफिक्स योग का उपयोग करके सभी नंबरों का योग गणना कर सकें।

इनपुट सरणी Arr[] और क्वेरी मैट्रिक्स Q[][] लें।
सेगमेंट ट्री लागू करने के लिए sgTreee[5 * length] सरणी लें।
प्रीफिक्स योग सरणी के लिए pSum[length] लें।
फंक्शन createTree(int min, int max, int pos, int sgT[], int arr[], int len) का उपयोग सेगमेंट ट्री में मान बनाने के लिए किया जाता है।
जांचें यदि (min == max) जिसका अर्थ है कि यह एक लीफ नोड है। sgT[pos] = arr[max] सेट करें।
midd = (min + max) / 2 लें।
loc1=2*pos+1 और loc2=2*pos+2 के लिए बाएं और दाएं सबट्री के लिए createTree(min, midd, loc1, sgT, arr, len) और createTree(midd + 1, max, loc2, sgT, arr, len) कॉल करें।
tmp1=sgT[loc1] और tmp2=sgT[loc2] लें और sgT[pos] को tmp1 या tmp2 जो भी अधिकतम हो उससे अपडेट करें।
फंक्शन preSum(int pSum4[], int arr4[], int len4) इनपुट सरणी लेता है और फॉर लूप का उपयोग करके प्रीफिक्स सरणी को अपडेट करता है।
सूचकांक 1 से अंतिम तक प्रत्येक तत्व के लिए, pSum4[j] = pSum4[j - 1] + arr4[j] अपडेट करें।
फंक्शन resQuery(int len3, int arr3[], int sgT3[], int pSum3[], int q1[][3], int qlen1) सभी इनपुट पैरामीटर्स लेता है और प्रत्येक क्वेरी के लिए परिणाम प्रिंट करता है।
resQuery() के अंदर, solQuery(int lpos, int rpos, int k, int len2, int arr2[], int sgT2[], int pSum2[]) को फॉर लूप का उपयोग करके प्रत्येक क्वेरी को एक-एक करके हल करने के लिए कॉल करें।
फंक्शन solQuery(int lpos, int rpos, int k, int len2, int arr2[], int sgT2[], int pSum2[]) क्वेरी को हल करता है और परिणाम लौटाता है।
यदि rpos - lpos > k तो -1 लौटाएं क्योंकि कोई समाधान संभव नहीं है।
maxVal = findMax(0, len2 - 1, lpos, rpos, 0, sgT2, arr2, len2) लें।
यदि maxVal < 0 तो maxVal को 0 पर सेट करें।
sum = pSum2[rpos] वेरिएबल लें।
यदि lpos > 0 तो sum -= pSum2[lpos - 1] सेट करें और result = sum + (k - (rpos - lpos)) * maxVal।
परिणाम लौटाएं।
फंक्शन findMax(int start, int end, int min1, int max1, int pos1, int sgT1[], int arr1[], int len1) रेंज lpos और rpos के बीच अधिकतम मान लौटाता है।
अंत में प्रत्येक क्वेरी के लिए परिणाम प्रिंट किया जाएगा। "No" यदि कोई समाधान नहीं है।

उदाहरण

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

void createTree(int min, int max, int pos, int sgT[], int arr[], int len) {
    if (min == max) {
        sgT[pos] = arr[max];
        return;
    }
    int midd = (min + max) / 2;
    int loc1 = 2 * pos + 1;
    int loc2 = 2 * pos + 2;
    createTree(min, midd, loc1, sgT, arr, len);
    createTree(midd + 1, max, loc2, sgT, arr, len);
    int tmp1 = sgT[loc1];
    int tmp2 = sgT[loc2];
    sgT[pos] = tmp1 > tmp2 ? tmp1 : tmp2;
}

int findMax(int start, int end, int min1, int max1, int pos1, int sgT1[], int arr1[], int len1) {
    int middle;
    if (min1 <= start) {
        if (max1 >= end) {
            return sgT1[pos1];
        }
    }
    if (end < min1 || start > max1) {
        return INT_MIN;
    }
    middle = (start + end) / 2;
    int loc1 = 2 * pos1 + 1;
    int loc2 = 2 * pos1 + 2;
    int lmax = findMax(start, middle, min1, max1, loc1, sgT1, arr1, len1);
    int rmax = findMax(middle + 1, end, min1, max1, loc2, sgT1, arr1, len1);
    int res = lmax > rmax ? lmax : rmax;
    return res;
}

int solQuery(int lpos, int rpos, int k, int len2, int arr2[], int sgT2[], int pSum2[]) {
    int result;
    if (rpos - lpos > k) {
        return -1;
    }
    int maxVal = findMax(0, len2 - 1, lpos, rpos, 0, sgT2, arr2, len2);
    if (maxVal < 0) {
        maxVal = 0;
    }
    int sum = pSum2[rpos];
    if (lpos > 0) {
        sum -= pSum2[lpos - 1];
    }
    result = sum + (k - (rpos - lpos)) * maxVal;
    return result;
}

void resQuery(int len3, int arr3[], int sgT3[], int pSum3[], int q1[][3], int qlen1) {
    int i;
    int result;
    for (i = 0; i < qlen1; i++) {
        result = solQuery(q1[i][0], q1[i][1], q1[i][2], len3, arr3, sgT3, pSum3);
        if (result == -1) {
            cout << endl << "Query " << i + 1 << ": " << "NO";
        } else {
            cout << endl << "Query " << i + 1 << ": " << result;
        }
    }
}

void preSum(int pSum4[], int arr4[], int len4) {
    pSum4[0] = arr4[0];
    int j;
    for (j = 1; j < len4; j++) {
        pSum4[j] = pSum4[j - 1] + arr4[j];
    }
}

int main() {
    int Arr[] = {1, 2, 4, -1};
    int length = sizeof(Arr) / sizeof(Arr[0]);
    int sgTreee[5 * length];
    createTree(0, length - 1, 0, sgTreee, Arr, length);
    int pSum[length];
    preSum(pSum, Arr, length);
    int Q[][3] = { { 0, 2, 2 }, { 0, 2, 1 }, { 3, 3, 1 }, { 0, 2, 3} };
    int qlen = sizeof(Q) / sizeof(Q[0]);
    resQuery(length, Arr, sgTreee, pSum, Q, qlen);
    return 0;
}

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा:

Query 1: 7
Query 2: NO
Query 3: NO
Query 4: 11