資料結構
網路
關係型資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++程式：查詢買家可購買的最大包裹數量
假設我們有兩個列表sales和buyers。sales中的每個元素都包含兩個值，形式為[日期, 價格]，這表示該包裹僅在該日期以該價格出售。buyers中的每個元素都以[付款日, 金額]的形式表示，這表示買家在付款日及之後有那麼多錢可用。如果每個買家最多隻能購買一個包裹，並且每個包裹只能賣給一個人，請找到可以購買的最大包裹數量。
因此，如果輸入類似於sales = [[0, 5], [0, 5], [0, 6], [1, 4], [1, 5], [3, 4]] buyers = [[0, 4], [0, 6],[1, 5]]，則輸出將為3，因為第一個人可以購買包裹[1, 4]。第二個人可以購買[0, 6]。最後一個人可以購買包裹[1, 5]。
為了解決這個問題，我們將遵循以下步驟：
ret := 0
根據付款日對buyers陣列進行排序，如果付款日相同，則按金額排序
定義一個集合pq（優先佇列）
對sales陣列進行排序
i := 0
對於sales中的每個專案it：
當 (i < buyers的大小 且 buyers[i, 0] <= it[0]) 時：
將buyers[i, 1]插入pq
(i 加 1)
j := 在pq中插入it[i]並使其排序的索引
如果j是一個有效的索引，則：
(ret 加 1)
從pq中刪除第j個元素
返回ret
示例
讓我們看看下面的實現，以便更好地理解：
#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);
}輸入
{{0, 5},{0, 5},{0, 6},{1, 4},{1, 5},{3, 4}}, {{0, 4},{0, 6},{1, 5}}輸出
3
更新於：2020年12月22日
201 次瀏覽
廣告