ต้นทุนน้อยที่สุดในการต่อไม้กาวใน C++

สมมติว่าเรามีไม้กาวบางชิ้นที่มีความยาวเป็นจำนวนเต็มบวก เราสามารถต่อไม้กาวสองชิ้นที่มีความยาว X และ Y ให้กลายเป็นชิ้นเดียวโดยจ่ายค่าใช้จ่าย X + Y ทำซ้ำจนเหลือไม้กาวชิ้นเดียว หาต้นทุนรวมน้อยที่สุด

ตัวอย่าง: [2,4,3] ผลลัพธ์: 14

ขั้นตอนการแก้ปัญหา (Min Heap / Priority Queue)

• สร้าง Min Heap (Priority Queue) ใส่ความยาวไม้กาวทั้งหมด
• ans := 0
• while Heap มีมากกว่า 1 องค์ประกอบ:
  • ดึงสองค่าน้อยที่สุดออกมา บวกกันได้ temp
  • ans += temp
  • ใส่ temp กลับเข้า Heap
• คืนค่า ans

ตัวอย่างโค้ด (C++)

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

class Solution {
public:
    int connectSticks(vector<int>& s) {
        priority_queue <int, vector<int>, greater<int> > pq;
        for(int i = 0; i < s.size(); i++) pq.push(s[i]);
        int ans = 0;
        while(pq.size() > 1) {
            int temp = pq.top(); pq.pop();
            temp += pq.top(); pq.pop();
            ans += temp;
            pq.push(temp);
        }
        return ans;
    }
};

int main() {
    vector<int> v = {2,4,3};
    Solution ob;
    cout << ob.connectSticks(v);
}

อินพุต

[2,4,3]

เอาต์พุต

14