在这个问题中，我们得到一个由 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 = 19output: 3
解决方案在这里，我们将使用二元提升的概念来解决问题。二元提升是将给定数字的值增加 2 的幂（通过翻转位完成），范围从 0 到 n。
我们将考虑一个类似于提升二叉树的概念，我们将在其中找到“p”指数的初始值。这是通过翻转位来增加的，确保该值不大于 x。现在，我们将考虑这个位置“p”的升力。
为此，我们将开始翻转数字的位，例如第 i 位翻转不会使总和大于 x。现在，根据 'p' 的值，我们有两种情况 -
目标位置位于 'position + 2 之间^i”和“位置 + 2^(i+1)”，其中第 i 次提升增加了值。或者，目标位置位于“position”和“position + 2^i”之间。
使用此我们将考虑索引位置。
示例说明我们解决方案工作原理的程序
#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的元素的详细内容。