POJ 1456(贪心)

 #include <string.h>
#include <iostream>
#include <queue>
#include <stdio.h> using namespace std; struct product{
int deadline;
int val;
friend bool operator<(product n1,product n2)
{
return n1.val<n2.val;
}
}q; bool mark[]; int main()
{
// freopen("in.txt","r",stdin);
priority_queue<product> s;
int m;
while(scanf("%d",&m)!=EOF)
{
for(int i=;i<m;i++)
{
scanf("%d%d",&q.val,&q.deadline);
s.push(q);
}
memset(mark,true,sizeof(mark));
int ans=;
while(!s.empty())
{
q=s.top();
s.pop();
for(int i=q.deadline;i>=;i--)
{
if(mark[i]) {
ans+=q.val;
mark[i]=false;
break;
}
}
}
printf("%d\n",ans);
}
return ;
}

http://poj.org/problem?id=1456

题意:在超市里,每一件物品都是有保质期的,而这个超市每卖一件商品所需要的时间是一天,问,在保质期结束前,可获得的最大利润是多少。

思路:有人说可以用并查集,但我做的并查集的题目不多,理解也不是很深,所以我也不知道怎么用并查集来做,但是,这道题很明显就是一个贪心的题目,所以我用的贪心的办法做的。首先,把商品按利润从大到小来进行排个序,然后把每一件商品都先试着在截止日期那天卖出去,如果那天被其他的商品占用了的话,那么在往前推一天,这样就可以求出最大利润。

我是用优先队列来做的。首先构造一个包含截止日期和价值的结构体,并在里面写个判断的操作。

然后构建一个结构体类的优先队列就可以了。

由于优先队列不怎么会,然后我还是以为优先队列的队顶是front,其实是top

上一篇:ajax提交form表单问题


下一篇:使用GET方式提交的表单遇到的问题