数据结构
网络
关系型数据库管理系统(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 次浏览
广告