Finden Sie das erste Element größer oder gleich X in der Präfixsumme von N Zahlen mithilfe des binären Liftings in C++

In diesem Problem erhalten wir ein Array arr[] bestehend aus N Zahlen und einem ganzzahligen Wert x. Unsere Aufgabe besteht darin, ein Programm zu erstellen, das binäres Boosting verwendet, um das erste Element in einer Präfixsumme von N Zahlen zu finden, das größer oder gleich X ist.

Die Präfixsumme 数组元素的强> ist ein Array, bei dem jedes Element die Summe aller Elemente im anfänglichen Array bis zu diesem Index ist.

Beispiel – array[] = {5, 2, 9, 4, 1}

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

Lassen Sie uns ein Beispiel nehmen, um dieses Problem zu verstehen,

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

Lösung

Hier verwenden wir das Konzept von Binary Boost, um das Problem zu lösen. Die binäre Förderung erhöht den Wert einer bestimmten Zahl um eine Potenz von 2 (durch Umdrehen von Bits) im Bereich von 0 bis N.

Wir betrachten ein Konzept ähnlich dem Boosted Binary Tree, bei dem wir den Anfangswert des „P“-Index finden. Dieser Wert wird durch das Umdrehen von Bits erhöht, um sicherzustellen, dass der Wert nicht größer als X ist. Nun betrachten wir die Auftriebskraft an dieser Position „P“.

Dazu beginnen wir mit dem Umdrehen der Bits der Zahl. Durch Umdrehen des i-ten Bits wird die Summe beispielsweise nicht größer als X. Abhängig vom Wert von „P“ haben wir nun zwei Fälle –

Zielposition liegt zwischen „Position + 2^i“ und „Position + 2^(i+1)“, wobei i-th Boost erhöht den Wert. Alternativ liegt die Zielposition zwischen „Position“ und „Position + 2^i“

Dabei betrachten wir die Indexposition

, um zu veranschaulichen, wie unser Lösungsprogramm funktioniert

rrree

Ausgabe

#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;
}

Das obige ist der detaillierte Inhalt vonFinden Sie das erste Element größer oder gleich X in der Präfixsumme von N Zahlen mithilfe des binären Liftings in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!