在這個問題中，我們得到一個由 N 個數字和一個整數值 x 組成的陣列 arr[]。我們的任務是建立一個程序，使用二進位提昇在 N 個數字的前綴和中尋找大於或等於 X 的第一個元素。
前綴和数组元素的强>是一個數組，其每個元素是初始數組中直到索引為止的所有元素的總和。
範例- array[] = {5, 2, 9, 4, 1 }
prefixSumArray[] = {5, 7, 16, 20, 21}
#讓我們舉個例子來理解這個問題，
Input: arr[] = {5, 2, 9, 4, 1}, X = 19
Output: 3登入後複製
解決方案
#在這裡，我們將使用二元提升的概念來解決問題。二元提升是將給定數字的值增加 2 的冪（透過翻轉位完成），範圍從 0 到 N。
我們將考慮一個類似於提升二元樹的概念，我們將在其中找到「P」指數的初始值。這是透過翻轉位元來增加的，確保該值不大於 X。現在，我們將考慮這個位置「P」的升力。
為此，我們將開始翻轉數字的位，例如第 i 位翻轉不會使總和大於 X。現在，根據'P' 的值，我們有兩種情況-
目標位置位於'position 2 之間^i」和「位置2^(i 1) ”，其中第i 次提升增加了值。或者，目標位置位於“position”和“position 2^i”之間。
使用此我們將考慮索引位置。
範例
說明我們解決方案工作原理的程式
#include
#include
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<登入後複製
輸出
The index of first elements of the array greater than the given number is 3
登入後複製
以上是使用C++中的二進位提升，在N個數字的前綴和中找到第一個大於或等於X的元素的詳細內容。更多資訊請關注PHP中文網其他相關文章！
