Chương trình tìm hiệu nhỏ nhất giữa các phần tử chọn từ các danh sách khác nhau trong C++

Mô tả bài toán

Cho danh sách các danh sách số. Chọn một số từ mỗi danh sách sao cho hiệu giữa số lớn nhất và nhỏ nhất được chọn là nhỏ nhất.

Ví dụ: lists = [[30, 50, 90], [85], [35, 70]] → chọn 90, 85, 70 → hiệu = 20.

Giải thuật

1. Sắp xếp từng danh sách con.
2. Khởi tạo hàng đợi ưu tiên (min-heap) lưu {giá trị, chỉ số danh sách, chỉ số phần tử}.
3. maxVal = giá trị lớn nhất trong các phần tử đầu tiên của các danh sách.
4. ret = INF.
5. Lặp khi kích thước heap = số danh sách:
   • Lấy phần tử nhỏ nhất (temp) từ heap.
   • Cập nhật ret = min(ret, maxVal - temp[0]).
   • Tăng chỉ số phần tử trong temp.
   • Nếu chưa hết danh sách tương ứng:
     • Cập nhật maxVal = max(maxVal, giá trị mới).
     • Cập nhật temp[0] = giá trị mới, đẩy lại vào heap.
6. Trả về ret.

Ví dụ minh họa (C++)

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

struct Cmp {
    bool operator()(vector<int>& a, vector<int>& b) {
        return !(a[0] < b[0]);
    }
};

class Solution {
public:
    int solve(vector<vector<int>>& lists) {
        int maxVal = INT_MIN;
        int ret = INT_MAX;
        priority_queue<vector<int>, vector<vector<int>>, Cmp> pq;
        int n = lists.size();
        for (int i = 0; i < n; i++) {
            sort(lists[i].begin(), lists[i].end());
            pq.push({lists[i][0], i, 0});
            maxVal = max(lists[i][0], maxVal);
        }
        while (pq.size() == n) {
            vector<int> temp = pq.top();
            pq.pop();
            ret = min(ret, maxVal - temp[0]);
            temp.back()++;
            if (temp.back() < lists[temp[1]].size()) {
                maxVal = max(maxVal, lists[temp[1]][temp.back()]);
                temp[0] = lists[temp[1]][temp.back()];
                pq.push(temp);
            }
        }
        return ret;
    }
};

int solve(vector<vector<int>>& lists) {
    return (new Solution())->solve(lists);
}

int main() {
    vector<vector<int>> v = {{30, 50, 90}, {85}, {35, 70}};
    cout << solve(v);
    return 0;
}

Đầu vào

{{30, 50, 90}, {85}, {35, 70}}

Đầu ra

20