在C ++中构造具有多个求和的目标数组

假设我们有一个整数目标数组。从包含全1的起始数组A中，我们可以执行以下过程-

• 将x视为当前数组中所有元素的总和。

• 在0到n的范围内选择索引i，其中n是数组的大小，并将索引i处的A的值设置为x。

• 我们可以根据需要多次重复此过程。

我们必须检查是否有可能从A生成目标数组，否则返回False。

因此，如果输入类似于[3,9,5]，则输出将为True，因为我们可以从索引[1,1,1]开始，然后在索引0处的总和为3，那么数组为[3 ，1,1]，则总和为5，在索引2，然后数组为[3,1,5]，然后总和为9，在索引1，所以数组为[3,9,5]。

为了解决这个问题，我们将遵循以下步骤-

• 和：= 0

• n：=目标大小

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• 总和：=总和+目标[i]

• 定义优先级队列pq，并使用目标数组对其进行初始化

• 当pq的顶部元素> sum时，执行-

• x：= pq的顶部元素

• 从pq中删除元素

• 在pq中插入2 * x-总和

• 和：= x

• 当sum与目标大小相同时返回true，否则返回false

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   bool isPossible(vector<int>& target) {
      lli sum = 0;
      int n = target.size();
      for (int i = 0; i < n; i++) {
         sum += target[i];
      }
      priority_queue<int> pq(target.begin(), target.end());
      while (pq.top() * 2 > sum) {
         int x = pq.top();
         pq.pop();
         pq.push(2 * x - sum);
         sum = x;
      }
      return sum == (int)target.size();
   }
};
main(){
   Solution ob;
   vector<int> v = {3,9,5};
   cout << (ob.isPossible(v));
}

输入值

{3,9,5}

输出结果

1