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: 3Hier 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
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!
