首页 > 代码库 > poj 1456 supermarket

poj 1456 supermarket

题目大意:

有很多物品要卖,每种物品都有自己的价值和截止日期,每个物品都必须在截止日期前卖出去,求最后获得的最大价值和是多少

思路:

优先队列

按照截止日期由大到小排序,从最大截止日期开始,一天天向前推直到1

如果某天是一个东西的截止日期,就把这件东西的价值加到优先队列里,每天都从优先队列里卖一个东西,ans+=q.top(),然后pop

最后输出ans

技术分享
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
int now,n,ans,maxn;
struct st
{
    int v,t;
    bool operator < (const st &a) const
    {
        if(t>a.t) return true;
        return false;
    }
}a[10101];
int main()
{
    while(cin>>n)
    {
        ans=0;
        priority_queue <int> q;
        for(int i=0;i<n;i++) 
        {
            scanf("%d%d",&a[i].v,&a[i].t);
        }
        sort(a,a+n);
        int k=0;
        int tm=a[0].t;
        for(int i=tm;i>=1;i--)
        {
            while(k<n&&a[k].t>=i) {q.push(a[k].v);k++;}
            if(!q.empty()){ans+=q.top();q.pop();}
        }
        printf("%d\n",ans);
    }
}
View Code

 

poj 1456 supermarket