Problem Description

To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they’re at the beach. Cow i has a minimum and maximum SPF rating (1 ≤ minSPFi ≤ 1,000; minSPFi ≤ maxSPFi ≤ 1,000) that will work. If the SPF rating is too low, the cow suffers sunburn; if the SPF rating is too high, the cow doesn’t tan at all……..
The cows have a picnic basket with L (1 ≤ L ≤ 2500) bottles of sunscreen lotion, each bottle i with an SPF rating SPFi (1 ≤ SPFi ≤ 1,000). Lotion bottle i can cover coveri cows with lotion. A cow may lotion from only one bottle.
What is the maximum number of cows that can protect themselves while tanning given the available lotions?

Input

Line 1: Two space-separated integers: C and L
Lines 2..C+1: Line i describes cow i’s lotion requires with two integers: minSPFi and maxSPFi
Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPFi and coveri

Output

A single line with an integer that is the maximum number of cows that can be protected while tanning

Sample Input

3 2?

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

Sample Output

2

題意：c頭牛曬太陽，每頭牛有一個防曬范圍，太低會曬傷，太高不能曬的充分，已知有L種防曬霜以及他們的數量與防曬范圍，現給牛涂防曬霜，問有多少頭牛能充分曬到太陽。?

思路

一開始只想到了用貪心算法，將牛按照防曬范圍的最小值升序排序，對每一種防曬霜，找出上限大于他且下限小于他的牛跟他匹配，枚舉所有防曬霜，將所有符合最小值小于該防曬霜的奶牛的最大值存儲，然后記錄答案。

錯誤代碼

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 2501 #define MOD 1001 #define E 1e-12 using namespace std; struct Node{int minn;int maxx; }spf[N]; int num[1001];//存儲每一種防曬霜的防曬范圍 bool vis[1001];//判斷防曬霜是否被用過 bool cmp(Node a,Node b) {if(a.maxx==b.maxx)return a.minn>b.minn;return a.maxx<b.maxx; } int main() {int c,l;scanf("%d%d\n",&c,&l);for(int i=1;i<=c;i++)//奶牛的防曬范圍scanf("%d%d",&spf[i].minn,&spf[i].maxx);for(int i=1;i<=l;i++)//桶排存儲每種防曬霜的防曬值{int x,y;scanf("%d%d",&x,&y);num[x]+=y;}int cnt=0;sort(spf+1,spf+c+1,cmp);for(int i=1;i<=1000;i++)//枚舉每一種防曬霜for(int j=1;j<=num[i];j++)//枚舉每一種防曬霜的防曬值for(int k=1;k<=c;k++)//枚舉每一頭牛if(spf[k].minn<=i&&i<=spf[k].maxx&&vis[k]==0)//如果當前的防曬霜未被用過且符合牛的防曬范圍{cnt++;vis[k]=1;break;}printf("%d\n",cnt);return 0; }

?

WA多次，查看大量題解后發現需要用優先隊列，將奶牛按照防曬范圍的最小值升序排序，將防曬霜也按照防曬值升序排序，從最小的防曬霜枚舉，將最小值小于等于該防曬霜的奶牛的最大值放入優先隊列之中，然后優先隊列最小值先出，就可將這些最大值中的最小的取出來，更新答案。

?

Source Program

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 2501 #define MOD 1001 #define E 1e-12 using namespace std; struct Cow {int maxx;int minn; }cow[N],cc; struct Sunscreen {int sum;int ans; }sunscreen[N],ss; priority_queue<int, vector<int>, greater<int> > q; bool cmp1(Cow x,Cow y) {return x.minn<y.minn; } bool cmp2(Sunscreen x,Sunscreen y) {return x.ans<y.ans; } int main() {int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)//牛的防曬范圍scanf("%d%d",&cow[i].minn,&cow[i].maxx);for(int i=1;i<=m;i++)//防曬霜的防曬值scanf("%d%d",&sunscreen[i].ans,&sunscreen[i].sum);sort(cow+1,cow+1+n,cmp1);//按牛的防曬下限升序排序sort(sunscreen+1,sunscreen+1+m,cmp2);//按防曬霜的防曬值升序排序int ans=0;int j=1;for(int i=1;i<=m;i++){while(j<=n&&cow[j].minn<=sunscreen[i].ans)//從最小的防曬霜枚舉，將最小值小于等于該防曬霜的奶牛的最大值放入優先隊列{q.push(cow[j].maxx);j++;}while(sunscreen[i].sum!=0&&!q.empty())//優先隊列最小值先出，可將所有最大值中的最小值取出，更新答案{int k=q.top();q.pop();if(k>=sunscreen[i].ans){ans++;sunscreen[i].sum--;}}}printf("%d\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的Sunscreen（POJ-3416）的全部內容，希望文章能夠幫你解決所遇到的問題。

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