约翰的奶牛对食物越来越挑剔了。
现在,商店有 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( ))判断是否可以满足奶牛的要求,最后统计答案输出