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]の場合、インデックス2で合計が5になり、配列が[3,1,5]になり、インデックス1で合計が9になるため、配列は[3,9,5]になります。

これを解決するには、次の手順に従います-

• 合計：=0

• n：=ターゲットのサイズ

• 初期化i：=0の場合、i

  • 合計：=合計+ターゲット[i]

• 優先キューpqを定義し、ターゲット配列で初期化します

• pq> sumの最上位要素である間、-

  • x：=pqの最上位要素

  • pqから要素を削除する

  • 2*x-合計をpqに挿入

  • 合計：=x

• 合計がターゲットのサイズと同じ場合は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