题目大意
多组数据,给定n件商品,每件商品有一个价格和截止日期。必须在截止日期前售出这个商品才可以获取对应的钱。每天只能售出一件商品,商品超过DDL即刻报废。求售货的最大收益。
解题思路
没想到时隔多年居然还能看到雨神的idea并且启发了我
首先考虑贪心,显然,在t时刻,售出ddl在t时刻之前的商品中,最大价值的t件商品,即可获得最大收益。
因此,我们需要设计一个小根堆用来动态维护上述的性质。
具体实现如下:
1. 如果该商品的过期时间,大于t时刻的堆中元素个数,说明t时刻之前一定可以找个时间把它卖出去,直接插入堆中。
2. 如果堆中元素=t,而t时刻仍然有商品可以卖出。此时比较堆内最小元素(堆顶)和待售商品的价值,若待售商品的价值高于堆顶,则取而代之。
代码实现
#include<iostream>//poj屑oj不让用万能头
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int n,m;
struct node{
int num,ddl;
}a[1000100];
int cmp(node x,node y){
return x.ddl<y.ddl;
};//以ddl排序
priority_queue<int,vector<int>,greater<int> > q;//小根堆
int main(){
while(scanf("%d",&n)!=EOF){
int ans=0;
for(int i=1;i<=n;i++){
scanf("%d %d",&a[i].num,&a[i].ddl);
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
//1.商品的ddl大于堆中元素个数,直接加入
if(a[i].ddl>q.size()){
q.push(a[i].num);
continue;
}
//2.待加入的商品价值,高于堆内最小值,可以舍弃最小值,加入此商品。
if(a[i].num>q.top()){
q.pop();
q.push(a[i].num);
}
}
while(!q.empty()){//统计和
ans+=q.top();
q.pop();
}
cout<<ans<<endl;
}
return 0;
}
0 条评论