正題

題目大意:https://jzoj.net/senior/#main/show/1246

---

題目大意

$n$頭牛，第$i$頭吃的東西價格大于$a_i$，鮮嫩度大于$b_i$。$m$個吃的，第$i$個價格為$c_i$，鮮嫩度為$d_i$。
求滿足所有奶牛的情況下最少要花多少錢。

---

解題思路

按照鮮嫩程度排序，然后枚舉奶牛時依次加入物品，對于每個奶牛，選擇滿足它要求的最便宜的物品，用$multiset$維護即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<set> #define ll long long using namespace std; const ll N=100100; multiset<int> s; struct node{ll v,w; }a[N],b[N]; ll n,m,ans; bool cmp(node x,node y) {return x.w>y.w;} int main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++)scanf("%lld%lld",&a[i].v,&a[i].w);for(ll i=1;i<=m;i++)scanf("%lld%lld",&b[i].v,&b[i].w);sort(a+1,a+1+n,cmp);sort(b+1,b+1+m,cmp);ll l=1;for(ll i=1;i<=n;i++){while(l<=m&&b[l].w>=a[i].w)s.insert(b[l++].v);multiset<int>::iterator it=s.lower_bound(a[i].v);if(it==s.end()){printf("-1");return 0;}ans+=*it;s.erase(it);}printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的jzoj1246-挑剔的美食家【set,贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。