Phân số nguyên tố thứ K nhỏ nhất (K-th Smallest Prime Fraction) trong C++

Cho mảng tăng dần chứa 1 và các số nguyên tố. Xét tất cả phân số p/q với p < q trong mảng. Tìm phân số thứ k nhỏ nhất. Trả về [p, q].

Ví dụ

A = [1,3,5,7], k = 2. Các phân số: 1/3, 1/5, 1/7, 3/5, 3/7, 5/7. Thứ 2 nhỏ nhất là 1/5 → [1,5].

Thuật toán Priority Queue

Khởi tạo hàng đợi ưu tiên với các phân số A[0]/A[i]. Lặp k lần: lấy phân số nhỏ nhất, nếu chưa đến lần thứ k thì đẩy phân số tiếp theo cùng mẫu số A[idx+1]/A[i] vào hàng đợi.

Chương trình C++

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

struct Data {
    double val, a, b;
    int idx;
    Data(double a, double b, int idx) : val(a/b), a(a), b(b), idx(idx) {}
};

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

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
        int n = A.size();
        priority_queue<Data, vector<Data>, Comparator> pq;
        for(int i=0; i
Kết quả
[1, 5]