前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >POJ3614防晒霜 这个贪心有点东西(贪心+优先队列)

POJ3614防晒霜 这个贪心有点东西(贪心+优先队列)

作者头像
风骨散人Chiam
发布2020-10-28 09:36:58
2960
发布2020-10-28 09:36:58
举报
文章被收录于专栏:CSDN旧文

这个题是说有C头牛去晒太阳,带了L瓶防晒霜,每瓶防晒霜都有一个SPF值(每瓶防晒霜都能解决一个最短路 ) 每头牛给出了他可以接受防晒霜的上限,和下限,每种防晒霜都给出了SPF值与数量。 从防晒霜的spf值最小开始贪心,每次将奶牛最大接受限度小的牛且符合条件选出,那么这头牛一定比其他牛接受范围更小,应该优先选择。

代码语言:javascript
复制
#include <bits/stdc++.h>
using namespace std;
const int maxn=3000;
struct cow
{
    int maxi;
    int mini;
    bool operator <(const cow & w)const
    {
        if(maxi==w.maxi)    return mini<w.mini;
        return maxi>w.maxi;
    }
    bool operator ==(const cow & w)const
    {
        if(maxi==w.maxi&&mini==w.mini)    return 1;
        return 0;
    }
} w ;
struct spf
{
    int sp;
    int nu;
    bool operator <(const spf& w)const
    {
        return sp>w.sp;
    }
} x;
int n,m,ans;
priority_queue<spf> s;
cow c[maxn];
priority_queue<cow>cw;
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>c[i].mini>>c[i].maxi;
    for(int i=0;i<m;i++)
        cin>>x.sp>>x.nu,s.push(x);
//    cout<<(s.top().sp)<<endl;
    while(!s.empty())
    {
        spf tem=s.top();
        s.pop();
        while(!cw.empty())cw.pop();
        for(int i=0;i<n;i++)
        {
            if(c[i].mini<=tem.sp&&c[i].maxi>=tem.sp)
            cw.push(c[i]);
        }
        if(!cw.empty()){
            cow temp=cw.top();
            c[find(c,c+n,temp)-c].maxi=-99;
            ans++;
            tem.nu--;
            if(tem.nu!=0) s.push(tem);
        }
        else ;
        if(ans==n) break;
    }
    cout<<ans<<endl;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/07/25 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档