数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 C++ 构造目标数组的多重和
假设我们有一个整数数组 target。从一个初始数组 A 开始，该数组包含所有 1，我们可以执行以下过程：
设 x 为当前数组中所有元素的总和。
选择索引 i，范围为 0 到 n，其中 n 是数组的大小，并将 A 中索引 i 处的值设置为 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]。
为了解决这个问题，我们将遵循以下步骤：
sum := 0
n := target 的大小
对于初始化 i := 0，当 i < n 时，更新（i 增加 1），执行：
sum := sum + target[i]
定义优先队列 pq，并用 target 数组初始化它
当 pq 的顶部元素 > sum 时，执行：
x := pq 的顶部元素
从 pq 中删除元素
将 2 * x - sum 插入 pq
sum := x
当 sum 等于 target 的大小时返回 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
更新于: 2020年6月8日
87 次浏览
广告