Trouver le premier élément supérieur ou égal à X dans la somme des préfixes de N nombres en utilisant le levage binaire en C++

Dans ce problème, nous obtenons un tableau arr[] composé de N nombres et d'une valeur entière x. Notre tâche est de créer un programme qui utilise le boosting binaire pour trouver le premier élément dans une somme préfixe de N nombres supérieure ou égale à X.

La somme du préfixe 数组元素的强> est un tableau où chaque élément est la somme de tous les éléments du tableau initial jusqu'à cet index.

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

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

Prenons un exemple pour comprendre ce problème,

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

Solution

Ici, nous utiliserons le concept de Binary Boost pour résoudre le problème. La promotion binaire augmente la valeur d'un nombre donné d'une puissance de 2 (effectuée en inversant les bits), allant de 0 à N.

Nous considérerons un concept similaire à l'arbre binaire boosté où l'on retrouvera la valeur initiale de l'index "P". Ceci est augmenté en retournant les bits, garantissant que la valeur n'est pas supérieure à X. Maintenant, nous allons considérer la force de portance à cette position « P ».

Pour ce faire, nous allons commencer à inverser les bits du nombre, par exemple inverser le i-ème bit ne rendra pas la somme supérieure à X. Maintenant, en fonction de la valeur de « P », nous avons deux cas :

la position cible est comprise entre « position + 2^i » et « position + 2^(i+1) », où i-ème Le levage augmente la valeur. Alternativement, la position cible est comprise entre "position" et "position + 2^i"

En utilisant cela, nous considérerons la position d'index

pour illustrer le fonctionnement de notre solution Programme

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

. sortie

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!