牛抹防晒霜

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

Inputcopy	Outputcopy
3 2 3 10 2 5 1 5 6 2 4 1	2

分析,开两个结构体,将分别存放范围,大小和数量,将范围放进优先队列,按照min由大到小排序,再将另一个结构体由大到小排序,然后贪心,如果在范围就加一 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct cow{
int min,max;
bool operator<(const cow &c)const{
return min<c.min;
}
}a[2505];
struct cow1{
int spf,num;
}b[2505];
bool cmp(cow1 a,cow1 b){
return a.spf>b.spf;
}
int main() {
int c, l,ans=0;
priority_queue< cow >que;
scanf("%d%d", &c, &l);
for (int i = 1; i <= c; i++) {
scanf("%d%d", &a[i].min,& a[i].max);
cow temp;
temp.min=a[i].min;
temp.max=a[i].max;
que.push(temp);
}
for(int i=1;i<=l;i++){
scanf("%d%d",&b[i].spf,&b[i].num);
}
sort(b+1,b+l+1,cmp);
for(int i=1;i<=c;i++){
cow tep=que.top();
for(int j=1;j<=l;j++){
if(b[j].spf>=tep.min&&b[j].spf<=tep.max&&b[j].num!=0){
b[j].num--;
ans++;
break;
}
}
que.pop();
}
printf("%d",ans);
}

最后

以上就是失眠便当为你收集整理的牛抹防晒霜的全部内容，希望文章能够帮你解决牛抹防晒霜所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。