สร้างอาร์เรย์เป้าหมายด้วยผลรวมหลายๆ ใน C++

คำอธิบายโจทย์

เริ่มจากอาร์เรย์ A ที่ทุกค่าเป็น 1 ทำซ้ำ: หาผลรวม x ของทุกค่าใน A, เลือก index i แล้วตั้ง A[i] = x ถามว่าสามารถสร้าง target array ได้หรือไม่

ตัวอย่าง

target = [3,9,5] → True

ขั้นตอน: [1,1,1] sum=3 → [3,1,1] sum=5 → [3,1,5] sum=9 → [3,9,5]

วิธีแก้ปัญหา (ย้อนกลับ)

1. คำนวณผลรวมทั้งหมดของ target
2. ใช้ Max Heap (priority queue) เก็บค่าทุกตัว
3. วนลูปเมื่อค่าสูงสุด > ผลรวมของที่เหลือ:
   • นำค่าสูงสุด x ออก
   • คำนวณค่าเดิม: 2*x - sum
   • นำค่าเดิมกลับเข้า heap
   • อัปเดต sum = x
4. ถ้า sum สุดท้าย == n (ขนาดอาร์เรย์) → True, มิฉะนั้น False

การทำงานของโค้ด

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;

class Solution {
public:
    bool isPossible(vector<int>& target) {
        lli sum = 0;
        int n = target.size();
        for(int x : target) sum += x;
        
        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 == n;
    }
};

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

อินพุต

{3,9,5}

เอาต์พุต

1