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]이고 합은 인덱스 1에서 9이므로 배열은 [3,9,5]입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

합계 :=0
n :=타겟의 크기
initialize i :=0의 경우, i
- 합계 :=합계 + 대상[i]
우선순위 큐 pq를 정의하고 대상 배열로 초기화
pq> sum의 최상위 요소인 동안 −
- x :=pq의 최상위 요소
- pq에서 요소 삭제
- insert 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}