C++ のバイナリ リフティングを使用して、N 数値のプレフィックス合計で X 以上の最初の要素を検索します。

この問題では、N 個の数値と整数値 x で構成される配列 arr[] が与えられます。私たちのタスクは、バイナリ プロモーションを使用して、N 個の数値のプレフィックスの合計で X 以上の最初の要素 を見つけるプログラムを 作成することです。

prefix sum 数组元素的强> は、各要素がそのインデックスまでの初期配列内のすべての要素の合計である配列です。

例 - array[] = {5, 2, 9, 4, 1}

prefixSumArray[] = {5, 7, 16, 20, 21}

この問題を理解するために例を挙げてみましょう。

Input: arr[] = {5, 2, 9, 4, 1}, X = 19
Output: 3

解決策

ここでは、バイナリ リフティングの概念を使用して問題を解決します。バイナリ プロモーションでは、0 から N までの範囲で、指定された数値の値が 2 のべき乗で増加します (ビットを反転することで行われます)。

ブースト二分木と同様の概念を検討し、「P」インデックスの初期値を見つけます。これはビットを反転することで増加し、値が X より大きくならないようにします。ここで、この位置「P」における揚力を考えます。

これを行うには、数値のビットの反転を開始します。たとえば、i 番目のビットを反転しても、合計は X より大きくなりません。ここで、「P」の値に応じて、2 つのケースがあります -

ターゲット位置は、「position 2^i」と「position 2^(i 1)」の間にあります。 "、i 番目のリフトにより値が増加します。または、目標位置は "position" と "position 2^i" の間です。

これを使用して、インデックスの位置を検討します。

Example

ソリューションがどのように機能するかを示すプログラム

#include <iostream>
#include <math.h>
using namespace std;
void generatePrefixSum(int arr[], int prefSum[], int n){
   prefSum[0] = arr[0];
   for (int i = 1; i < n; i++)
      prefSum[i] = prefSum[i - 1] + arr[i];
}
int findPreSumIndexBL(int prefSum[], int n, int x){
   int P = 0;
   int LOGN = log2(n);
   if (x <= prefSum[0])
      return 0;
   for (int i = LOGN; i >= 0; i--) {
      if (P + (1 << i) < n &&
         prefSum[P + (1 << i)] < x) {
         P += (1 << i);
      }
   }
   return P + 1;
}
int main(){
   int arr[] = { 5, 2, 9, 4, 1 };
   int X = 19;
   int n = sizeof(arr) / sizeof(arr[0]);
   int prefSum[n] = { 0 };
   generatePrefixSum(arr, prefSum, n);
   cout<<"The index of first elements of the array greater than the given number is ";
   cout<<findPreSumIndexBL(prefSum, n, X);
   return 0;
}

出力

The index of first elements of the array greater than the given number is 3

以上がC++ のバイナリ リフティングを使用して、N 数値のプレフィックス合計で X 以上の最初の要素を検索します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。