首页 > 代码库 > 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); } }
poj 1456 supermarket
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。