超市(堆)
Supermarket
https://ac.nowcoder.com/acm/problem/50995
题目描述
超市里有N件商品,每件商品都有利润pi和过期时间di,每天只能卖一件商品,过期商品不能再卖。
求合理安排每天卖的商品的情况下,可以得到的最大收益是多少。
输入格式
输入包含多组测试用例。
每组测试用例,以输入整数N开始,接下来输入N对pi和di,分别代表第i件商品的利润和过期时间。
在输入中,数据之间可以自由穿插任意个空格或空行,输入至文件结尾时终止输入,保证数据正确。
输出格式
对于每组产品,输出一个该组的最大收益值。
每个结果占一行。
数据范围
0≤N≤10000,
1≤pi,di≤10000
Slove:
按照日期从小到达排序,维护一个堆heap,
对于第i种物品如果今天卖他但是a[i].date<heap.size(),也就是说第i个物品已经过期了,所以你要pop掉价值小的,来卖第i个物品
最后堆种的物品就是需要卖掉能得到最大价值的物品
代码
#include<bits/stdc++.h> using namespace std; struct wmy { int price; int date; } a[10000]; bool cmp(wmy a,wmy b) { return a.date<b.date; } int main() { int n; while(scanf("%d",&n)!=EOF) { int i,sum=0; for(i=0; i<n; i++) scanf("%d%d",&a[i].price,&a[i].date); sort(a,a+n,cmp); priority_queue<int,vector<int>,greater<int>>heap; for(i=0; i<n; i++) { heap.push(a[i].price); if(a[i].date<heap.size()) heap.pop(); } while(!heap.empty()) { sum=sum+heap.top(); heap.pop(); } printf("%d\n",sum); } return 0; }