假设我们有一个整数目标数组。从包含全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