資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告