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

Giả sử chúng ta có một danh sách các danh sách, chúng ta phải tìm sự khác biệt nhỏ nhất có thể được hình thành bằng cách chọn một giá trị từ mỗi danh sách và lấy sự khác biệt giữa số lớn nhất và số nhỏ nhất của phần tử đã chọn.

Vì vậy, nếu đầu vào giống như danh sách =[[30, 50, 90], [85], [35, 70]], thì đầu ra sẽ là 20, như chúng ta có thể lấy 90, 85, 70 và 90 - 70 =20

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• maxVal:=-inf

• ret:=inf

• xác định hàng đợi ưu tiên pq

• n:=kích thước của danh sách

• để khởi tạo i:=0, khi i

  • sắp xếp danh sách mảng [i]

  • chèn {danh sách [i, 0], i, 0} vào pq

  • maxVal:=tối đa danh sách [i, 0] và maxVal

• trong khi kích thước của pq giống với n, do -

  • Xác định một mảng temp =top of pq

  • xóa phần tử hàng đầu khỏi pq

  • ret:=tối thiểu ret và (maxVal - temp [0])

  • tăng phần tử nhiệt độ cuối cùng

  • nếu phần tử cuối cùng của temp

    • maxVal:=tối đa của maxVal và danh sách [temp [1], phần tử cuối cùng của temp]

    • temp [0]:=list [temp [1], phần tử cuối cùng của temp]

    • chèn tạm thời vào pq

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

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

Đầu ra

20