C ++の範囲[L、R]で最大K個の移動の数の合計を最大化します

整数を含む配列Arr[]とクエリを含む2D配列Qが与えられます。各クエリには、lpos、rpos、Kの3つの値が含まれています。1つのステップでインデックスiから次のインデックスi + 1に移動することも、そのインデックスにとどまることができます。最大Kステップでlposからrposに移動できます。左端の数字を含め、各ステップですべての数字を追加します。目標は、最大K回の移動で合計を最大化することです。 Kステップでlposからrposに移動できない場合は、「いいえ」と出力します。もっと理解しましょう。

このためのさまざまな入出力シナリオを見てみましょう-

で − arr [] ={1、2、4、-1};

Q [] [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）

2番目のクエリ：-

最大1ステップでインデックス0から2に移動することはできません。 「いいえ」を印刷

3番目のクエリ：-

最大1ステップでインデックス3から3に移動することはできません。 「いいえ」を印刷

4番目のクエリ：-

最大3ステップでインデックス0から2に移動できます：-

ステップ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：いいえ

クエリ2:10

説明 −

最初のクエリ：-

最大1ステップでインデックス0から2に移動することはできません。 「いいえ」を印刷します

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[][]をクエリします。

• セグメントツリーを実装するための配列として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 *の左右のサブツリーに対してcreateTree（min、midd、loc1、sgT、arr、len）およびcreateTree（midd + 1、max、loc2、sgT、arr、len）を呼び出します。 pos+2。

• tmp1 =sgT[loc1]およびtmp2=sgT [loc2]を取得し、sgT[pos]をtmp1またはtmp2のいずれか大きい方で更新します。

• 関数preSum（int pSum4 []、int arr4 []、int len4）は、入力配列を受け取り、forループを使用してプレフィックス配列を更新します。

• インデックス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 []）を呼び出して、forループを使用して各クエリを1つずつ解決します。

• 関数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の間の最大値を返します。

• （min1 <=start）および（max1> =end）の場合、オーバーラップがあるため、sgT1[pos1]を返します。

• （end max1）の場合、範囲外が発生しているため、INT_MINを返します。

• 左右のサブツリーの再帰呼び出しを使用してlmaxとrmaxを計算し、最大2つを返します。

• 最後に、クエリごとに結果が出力されます。解決策がない場合は「いいえ」

例

#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