P2869 [USACO07DEC]Gourmet Grazers G

约翰的奶牛对食物越来越挑剔了。
现在,商店有 m 份牧草可供出售,奶牛食量很大,每份牧草仅能供一头奶牛食用。
第 i 份牧草的价格为 pi​,口感为 qi。
约翰一共有 n 头奶牛,他要为每头奶牛订购一份牧草,第 i 头奶牛要求 它的牧草价格不低于 ai​,口感不低于 bi。
请问,约翰应该如何为每头奶牛选择牧草,才能让他花的钱最少?
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
struct hp
{
    ll pri,fav;
}a[maxn],b[maxn];
int cmp(hp a,hp b)
{
    return a.fav>b.fav;
}
multiset<ll> q;
multiset<ll>::iterator s;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {scanf("%lld %lld",&a[i].pri,&a[i].fav);}
    for(int i=1;i<=m;i++)
    {scanf("%lld %lld",&b[i].pri,&b[i].fav);}
    sort(a+1,a+1+n,cmp);
    sort(b+1,b+1+m,cmp);
    int now=1;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        while(now<=m&&(b[now].fav>=a[i].fav))q.insert(b[now].pri),now++;
        s=q.lower_bound(a[i].pri);
        if(s==q.end())
        {
            printf("-1");
            return 0;
        }
        ans+=*s;
        q.erase(q.find(*s));
    }
    printf("%lld\n",ans);
    return 0;
}

 

 

思路:

因为题目中有两个需要考虑的变量,但是在价格相同的时候,牧草口感的高低对结果没有明显的影响,但是尽量将牧草给需要更加好口感牧草的奶牛会使得答案更优,所以我们先考虑将牧草和奶牛按照口感从高到低的顺序排序。再依次将满足当下奶牛需求的牧草放入,multiset<int>的顺序容器中,用lower_bound找寻满足当下奶牛口感的最便宜的牧草,并且这样做的显然好处是不影响相应后面的奶牛(不如说许多有最低限度的题目都可以这么去思考),最后(multiset<int>::iterator s !=q.end( ))判断是否可以满足奶牛的要求,最后统计答案输出

上一篇:STL教程(六): 关联容器--unordered_set/unordered_multiset


下一篇:Guava常用的集合扩展