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

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

आइए इसके लिए विभिन्न इनपुट आउटपुट परिदृश्य देखें -

में − Arr[] ={1, 2, 4, -1};

क्यू[][3] ={{ 0, 2, 2}, { 0, 2, 1}, { 3, 3, 1}, { 0, 2, 3}};

बाहर -

प्रश्न 1:7

प्रश्न 2:नहीं

प्रश्न 3:नहीं

प्रश्न 4:11

स्पष्टीकरण -

पहली क्वेरी:-

हम अधिकतम 2 चरणों में इंडेक्स 0 से 2 पर जा सकते हैं:-

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

चरण 2:- इंडेक्स 1 से 2 ( 3+4=7)

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

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

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

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

चौथी क्वेरी:-

हम अधिकतम 3 चरणों में इंडेक्स 0 से 2 पर जा सकते हैं:-

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

चरण 2:- इंडेक्स 1 से 2 ( 3+4=7)

चरण 3:- इंडेक्स 2 (7+4=11) पर बने रहें

में - एआर [] ={ 1, 2, 3, 3, 2 }; क्यू[][3] ={{ 0, 3, 2}, { 1, 4, 3}};

बाहर -

प्रश्न 1:नहीं

प्रश्न 2:10

स्पष्टीकरण -

पहली क्वेरी:-

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

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

हम अधिकतम 3 चरणों में अनुक्रमणिका 1 से 4 पर जा सकते हैं:-

चरण 1:- इंडेक्स 1 से 2 ( 2+3=5)

चरण 2:- इंडेक्स 2 से 3 ( 5+3=8)

चरण 3:- इंडेक्स 3 से 4 ( 8+2=10 )

नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है

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

• इनपुट सरणी Arr[] और क्वेरी मैट्रिक्स Q[][] लें।

• सेगमेंट ट्री को लागू करने के लिए sgTree[5 * length] को सरणी के रूप में लें।

• pSum [लंबाई] को उपसर्ग योग सरणी के रूप में लें।

• फ़ंक्शन createTree(int min, int max, int pos, int sgT[], int arr[], int len) का उपयोग सेगमेंट ट्री में मान बनाने के लिए किया जाता है।

• जांचें कि क्या (न्यूनतम ==अधिकतम) जिसका अर्थ है कि यह एक पत्ता नोड है। sgT [pos] =arr [अधिकतम] सेट करें।

• मध्य लें =(न्यूनतम + अधिकतम) / 2.

• कॉल createTree(min, midd, loc1, sgT, arr, len) और createTree(mid + 1, max, loc2, sgT, arr, len) लेफ्ट और राइट सबट्री के लिए जहां loc1=2*pos+1 और loc2=2* स्थिति+2.

• 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 के रूप में सेट करें

• परिवर्तनीय योग =pSum2[rpos] लें।

• यदि lpos> 0 तो योग -=pSum2[lpos - 1] और परिणाम =योग + (k - (rpos - lpos)) * maxVal सेट करें।

• वापसी परिणाम।

• फ़ंक्शन findMax(int ​​start, int end, int min1, int max1, int pos1, int sgT1[], int arr1[], int len1) रेंज lpos और rpos के बीच अधिकतम मान देता है।

• अगर (min1 <=start) और (max1>=end) तो ओवरलैप होने पर sgT1[pos1] लौटाएं।

• अगर (अंत max1) तो सीमा से बाहर हो रहा है इसलिए INT_MIN लौटाएं।

• बाएँ और दाएँ सबट्री के लिए पुनरावर्ती कॉल का उपयोग करके lmax और rmax की गणना करें और अधिकतम दो लौटाएँ।

• अंत में प्रत्येक प्रश्न के लिए परिणाम मुद्रित किया जाएगा। "नहीं" अगर कोई समाधान नहीं है

उदाहरण

#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