题目链接

题目大意

多组数据,给定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 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注