题目描述
超市里有N件商品,每件商品都有利润$p_i$和过期时间$d_i$,每天只能卖一件商品,过期商品不能再卖。
求合理安排每天卖的商品的情况下,可以得到的最大收益是多少。
样例
输入样例:
4 50 2 10 1 20 2 30 1
7 20 1 2 1 10 3 100 2 8 2
5 20 50 10
输出样例:
80
185
算法1
(贪心) $O(n)$
首先明确题意,要求在有限时间内的最大价值,势必会出现剔除一些商品的情况,按照贪心思想,剔除的商品应该是价值最小的商品。
1.对商品的时间进行排序
2.创建一个小跟堆,然后将商品push到小跟堆里。
3.当小跟堆的商品数量比当前商品的期限$d_i$大的时候,说明在$d_i$的时间段内,需要卖的东西数量大于$d_i$,所以需要剔除商品。
4.堆里留下的商品就是最大值。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
typedef pair<int, int> PII;
int n;
int main(){
while (cin >> n){
int res = 0;
vector<PII> a(n);
priority_queue<int, vector<int>, greater<int>> heap;
for (int i = 0; i < n; i ++) cin >> a[i].second >> a[i].first;
sort(a.begin(), a.end());
for (int i = 0; i < n; i ++){
heap.push(a[i].second);
if (heap.size() > a[i].first) heap.pop();
}
while (heap.size()){
res += heap.top();
heap.pop();
}
cout << res << endl;
}
return 0;
}