Sunscreen

poj 3614

luogu 2887

題目大意：

有n個(gè)人，每個(gè)人要求選一個(gè)價(jià)值在$min{n}_i$到$max{x}_i$的物品，現(xiàn)在有m件物品，每件的價(jià)值是$sp{f}_i$，可以選$cove{r}_i$次，問(wèn)最多可以滿(mǎn)足多少個(gè)人的要求

輸入樣例

3 2 3 10 2 5 1 5 6 2 4 1

輸出樣例

2

數(shù)據(jù)范圍

$1\le N,M\le 2500$
$1\le minSPFi\le maxSP{F}_i\le 1,000$

解題思路：

先按每個(gè)人的minn按從大到小排一遍序，然后每個(gè)人都盡量選價(jià)值大的物品然后計(jì)算結(jié)果即可

代碼：

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,num,ans; struct rec {int minn,maxx; }s[3000]; struct recc {int spf,cover; }S[3000]; bool cmp(rec x,rec y){return x.minn>y.minn;}//從大到小 bool cmpp(recc x,recc y){return x.spf>y.spf;}//從大到小 int main() {scanf("%d %d",&n,&m);for(int i=1;i<=n;++i)scanf("%d %d",&s[i].minn,&s[i].maxx);for(int i=1;i<=m;++i)scanf("%d %d",&S[i].spf,&S[i].cover);sort(s+1,s+1+n,cmp);//排序sort(S+1,S+1+m,cmpp);for (int i=1;i<=n;++i){num=0;for(int j=1;j<=m;++j)if(S[j].cover&&S[j].spf<=s[i].maxx&&S[j].spf>=s[i].minn)//可以選{num=j;//選break;} if(num){S[num].cover--;//數(shù)量減一ans++;//結(jié)果加一}}printf("%d",ans); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【贪心】Sunscreen（poj 3614/luogu 2887）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。