Computer >> Máy Tính >  >> Lập trình >> C ++

Xây dựng mảng đích với nhiều tổng trong C ++

Giả sử chúng ta có một mảng các số nguyên đích. Từ một mảng bắt đầu A bao gồm tất cả các số 1, chúng ta có thể thực hiện quy trình sau -

  • Coi x là tổng của tất cả các phần tử hiện có trong mảng của chúng ta.

  • Chọn chỉ mục i, trong phạm vi từ 0 đến n, trong đó n là kích thước của mảng và đặt giá trị của A tại chỉ mục i thành x.

  • Chúng ta có thể lặp lại quy trình này nhiều lần nếu cần.

Chúng ta phải kiểm tra xem có thể tạo mảng mục tiêu từ A hay không trả về False.

Vì vậy, nếu đầu vào là [3,9,5], thì đầu ra sẽ là True, vì chúng ta có thể bắt đầu với chỉ số [1,1,1], sau đó tổng là 3 ở chỉ số 0, sau đó mảng là [3 , 1,1], sau đó tổng là 5, tại chỉ số 2, sau đó mảng là [3,1,5], sau đó tổng là 9, tại chỉ số 1, vì vậy mảng là [3,9,5].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • tổng:=0

  • n:=kích thước của mục tiêu

  • để khởi tạo i:=0, khi i

    • sum:=sum + target [i]

  • Xác định hàng đợi ưu tiên pq và khởi tạo nó bằng mảng đích

  • trong khi phần tử trên cùng của pq> sum, do -

    • x:=phần tử hàng đầu của pq

    • xóa phần tử khỏi pq

    • chèn 2 * x - sum vào pq

    • tổng:=x

  • trả về true khi tổng bằng với kích thước của target, ngược lại là false

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ 

#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));
}

Đầu vào 

{3,9,5}

Đầu ra 

1