Super Ugly Number ใน C++

Super Ugly Numbers คือจำนวนเต็มบวกที่ตัวประกอบเฉพาะ (prime factors) ทั้งหมดอยู่ในรายการเฉพาะ primes ที่กำหนด ต้องหา Super Ugly Number ตัวที่ n

ตัวอย่าง: n = 12, primes = [2, 7, 13, 19] ผลลัพธ์: 32
ลำดับ 12 ตัวแรก: [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]

ขั้นตอนการแก้ปัญหา (Min Heap + Multiple Pointers)

• โครงสร้าง Data เก็บ num, prime, idx
• ถ้า n == 1 คืน 1
• อาร์เรย์ v ขนาด n+1 เติม 1
• Min Heap pq ใส่ Data(primes[i], primes[i], 2) สำหรับทุก prime
• วน i จาก 2 ถึง n:
  • ดึง curr จาก pq val := curr.num
  • v[i] := val
  • อัปเดต curr.num := curr.prime * v[curr.idx], curr.idx++ ใส่กลับ pq
  • while val == pq.top().num (กันซ้ำ):
    • ดึง curr อัปเดตเหมือนกัน ใส่กลับ
• คืน v[n]

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

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

struct Data {
    int num, prime, idx;
    Data(int a, int b, int c) {
        num = a;
        prime = b;
        idx = c;
    }
};

struct Comparator {
    bool operator()(Data a, Data b) {
        return !(a.num < b.num);
    }
};

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        if(n == 1) return 1;
        vector <int> v(n + 1, 1);
        priority_queue < Data, vector < Data >, Comparator > pq;
        for(int i = 0; i < primes.size(); i++) {
            pq.push(Data(primes[i], primes[i], 2));
        }
        for(int i = 2; i <= n; i++) {
            Data curr = pq.top();
            pq.pop();
            int val = curr.num;
            v[i] = val;
            curr.num = curr.prime * v[curr.idx];
            curr.idx++;
            pq.push(curr);
            while(val == pq.top().num) {
                curr = pq.top();
                pq.pop();
                curr.num = curr.prime * v[curr.idx];
                curr.idx++;
                pq.push(curr);
            }
        }
        return v[n];
    }
};

int main() {
    Solution ob;
    vector<int> v = {2,7,13,19};
    cout << (ob.nthSuperUglyNumber(12, v));
}

อินพุต

12 [2,7,13,19]

เอาต์พุต

32