Chương trình tìm số lượng gói tối đa mà người mua có thể mua bằng C ++

Giả sử chúng ta có hai danh sách bán hàng và người mua. Mỗi phần tử trong bán hàng chứa hai giá trị ở dạng [ngày, giá], điều này cho biết gói chỉ có sẵn để bán vào ngày đó với mức giá nhất định đó. Và mỗi phần tử trong người mua ở dạng [ngày lĩnh lương, số tiền] chỉ ra rằng người mua có số tiền đó để chi tiêu vào ngày lĩnh lương và sau đó. Nếu mỗi người mua có thể mua nhiều nhất một gói và mỗi gói chỉ có thể được bán cho một người, hãy tìm số gói tối đa có thể mua.

Vì vậy, nếu đầu vào là bán hàng =[[0, 5], [0, 5], [0, 6], [1, 4], [1, 5], [3, 4]] người mua =[[ 0, 4], [0, 6], [1, 5]], thì đầu ra sẽ là 3, vì người đầu tiên có thể lấy gói [1, 4]. Người thứ hai có thể lấy [0, 6]. Và người cuối cùng có thể nhận gói hàng [1, 5].

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

• ret:=0

• sắp xếp người mua mảng dựa trên ngày lĩnh lương, nếu các ngày trả lương giống nhau, hãy sắp xếp họ theo số tiền

• xác định một tập hợp pq

• sắp xếp mảng bán hàng

• i:=0

• đối với từng mặt hàng mà nó được bán -

  • while (i

    • chèn người mua [i, 1] vào pq

    • (tăng i lên 1)

  • j:=index của pq để chèn nó [i] intp pq và sắp xếp nó

  • nếu j là một chỉ mục hợp lệ, thì -

    • (tăng ret lên 1)

    • xóa phần tử thứ j khỏi pq

• trả lại ret

Ví dụ

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   static bool cmp(vector<int>& a, vector<int>& b) {
      return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
   }
   int solve(vector<vector<int>>& sales, vector<vector<int>>& buyers) {
      int ret = 0;
      sort(buyers.begin(), buyers.end());
      multiset<int> pq;
      sort(sales.begin(), sales.end(), cmp);
      int i = 0;
      for (auto& it : sales) {
         while (i < buyers.size() && buyers[i][0] <= it[0]) {
            pq.insert(buyers[i][1]);
            i++;
         }
         auto j = pq.lower_bound(it[1]);
         if (j != pq.end()) {
            ret++;
            pq.erase(j);
         }
      }
      return ret;
   }
};
int solve(vector<vector<int>>& sales, vector<vector<int>>& buyers) {
   return (new Solution())->solve(sales, buyers);
}
int main(){
   vector<vector<int>> sales = {{0, 5},{0, 5},{0, 6},{1, 4},{1, 5},{3, 4}};
   vector<vector<int>> buyers = {{0, 4},{0, 6},{1, 5}};
   cout << solve(sales, buyers);
}

Đầu vào

{{0, 5},{0, 5},{0, 6},{1, 4},{1, 5},{3, 4}}, {{0, 4},{0, 6},{1, 5}}

Đầu ra

3