Xây dựng mảng mục tiêu với nhiều tổng trong C++

Cho mảng target các số nguyên. Từ mảng A ban đầu toàn số 1, ta có thể thực hiện: lấy x = tổng các phần tử hiện tại, chọn chỉ số i, gán A[i] = x. Lặp lại bao nhiêu lần cũng được. Kiểm tra có thể tạo được target từ A không.

Ví dụ: target = [3,9,5], đầu ra True. Bắt đầu [1,1,1], tổng=3 tại chỉ số 0 → [3,1,1], tổng=5 tại chỉ số 2 → [3,1,5], tổng=9 tại chỉ số 1 → [3,9,5].

Giải pháp

Tư duy ngược: từ target quay về mảng toàn 1. Luôn chọn phần tử lớn nhất (phải là tổng trước đó).

• Tính sum = tổng target
• Dùng priority queue (max-heap) chứa các phần tử target
• Lặp: lấy x = phần tử lớn nhất. Nếu x * 2 > sum: phần tử này vừa được cập nhật
  • Thay x bằng 2*x - sum (giá trị cũ)
  • Cập nhật sum = x
• Dừng khi phần tử lớn nhất * 2 ≤ sum
• Kết quả: true nếu sum == n (kích thước mảng), ngược lại false

Ví dụ mã C++

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

int main() { 
    Solution ob; 
    vector<int> v = {3,9,5}; 
    cout << (ob.isPossible(v)); 
    return 0; 
}

Đầu vào

{3,9,5}

Đầu ra

1