本文主要是介绍ACM 贪心 Sunscreen，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
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?
* Line 1: Two space-separated integers: C and L
* Lines 2..C+1: Line i describes cow i's lotion requires with two integers: minSPFiand maxSPFi
* Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPFi and coveri
A single line with an integer that is the maximum number of cows that can be protected while tanning
3 2 3 10 2 5 1 5 6 2 4 1Sample Output
2
题意：
给出每种牛的需要的防晒霜强度的范围，以及防晒霜的数量和强度，求出最多可有有多少头奶牛不会被烧烤
分析：
很明显想到用贪心做，把范围的最小值按照从小到大排序，防晒霜的强度同样如此，之后用优先队列，首先我们将符合条件的牛的最大值加入，每次调出最小值看是否大于等于某瓶防晒霜，如果符合，就多一头牛；
代码：
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
struct Cow
{
int l;//最小值
int r;//最大值
}cow[2505];
struct Fang
{
int du;
int sum;
}fang[2505];
int C,L;
priority_queue<int, vector<int>, greater<int> > q;//每次出来最小值的优先队列
bool cmp(const Cow &a,const Cow &b)
{
if(a.l!=b.l) return a.l<b.l;
else if(a.r!=b.r) return a.r<b.r;
else return 0;
}
bool cmp1(const Fang &a,const Fang &b)
{
return a.du<b.du;
}
int main()
{
int i,j,ans;
while(scanf("%d %d",&C,&L)!=EOF)
{
for(i=0;i<C;i++)
scanf("%d %d",&cow[i].l,&cow[i].r);
for(j=0;j<L;j++)
scanf("%d %d",&fang[j].du,&fang[j].sum);
sort(cow,cow+C,cmp);
sort(fang,fang+L,cmp1);
ans=0;
j=0;
for(i=0;i<L;i++)
{
while(j<C&&cow[j].l<=fang[i].du)
{
q.push(cow[j].r);
j++;
}
while(fang[i].sum!=0&&!q.empty())
{
int head=q.top();
q.pop();
if(fang[i].du<=head)
{
ans++;
fang[i].sum--;
}
}
}
printf("%d\n",ans);
}
return 0;
}
这篇关于ACM 贪心 Sunscreen的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
