每个商品有收益p和时限d 求时限内的最大收益
法一: 当从前向后贪心的时候 可能会出现反悔的情况 这样局部最优解和全局最优解有不一致. 为了解决反悔问题,我们可以采用倒序贪心的方式
int main()
{
while(scanf("%d",&n)!=EOF)
{
while(q.size()) q.pop();
memset(s,0,sizeof s);
for(int i=1;i<=n;i++)
{
int x=read(),y=read();
s[i]=(Node){x,y};
}
sort(s+1,s+n+1,cmp);
int t=0,ans=0;
while(t<n)
{
do{
t++;
q.push( s[t].p );
}while(s[t].d==s[t+1].d) ;
for(int i=1;i<=s[t].d-s[t+1].d&&q.size();i++)
ans+=q.top(),q.pop();
}
printf("%d\n",ans);
}
return 0;
}
法二: 反悔堆 用于处理反悔贪心问题
维护一个堆,用后面集合的更优秀的解来替换前面集合较差的解。每次排除最劣解,加入较优解
原文链接: https://www.cnblogs.com/juruoHBr/p/15831461.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/187132
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!