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
Sample Input
3 2
3 10
2 5
1 5
6 2
4 1
Sample Output
2 題意：
有C個奶牛去曬太陽 (1 <=C <= 2500)，每個奶牛各自能夠忍受的陽光強度有一個最小值和一個最大值，太大太小都沒有作用。
而剛開始的陽光的強度非常大，奶牛都承受不住，然後奶牛就得塗抹防曬霜，防曬霜的作用是讓陽光照在身上的陽光強度固定為某個值。
那麼為了不讓奶牛燙傷，又不會沒有效果。
給出了L種防曬霜。每種的數量和固定的陽光強度也給出來了
每個奶牛隻能抹一瓶防曬霜，最後問能夠享受曬太陽的奶牛有幾個。
思路：
防曬霜從小到大排序
奶牛能承受的最小值從小到大排序
從最小的防曬霜枚舉，将所有符合最小值小于等于該防曬霜的奶牛的最大值放入優先隊列之中。
然後優先隊列是小值先出
因為把牛能承受的最小值從小到大排序後，牛能承受的最大值越小，則這隻牛能選擇的防曬霜的種類越受限，也就是說如果一隻牛能承受1-3，另一隻能承受1-5，有一個2的防曬霜，則這個防嗮爽優先給能承受1-3的使用。
是以就可以将這些最大值中的最小的取出來
代碼：
#include<stdio.h>
#include<stack>
#include<algorithm>
#include<queue>
#include<iostream>
#include<string.h>
#include<string>
using namespace std;
struct node
{
int begin;
int end;
} cow[2501];
struct node1
{
int number;
int spf;
} l[2501];
bool cmp(struct node a,struct node b)
{
return a.begin<b.begin;
}
bool cmp1(struct node1 a,struct node1 b)
{
return a.spf<b.spf;
}
int main()
{
int m,n,logo=0;
scanf("%d%d",&m,&n);
for(int i=0; i<m; i++)
scanf("%d%d",&cow[i].begin,&cow[i].end);
// cin>>cow[i].begin>>cow[i].end;
for(int i=0; i<n; i++)
scanf("%d%d",&l[i].spf,&l[i].number);
//cin>>l[i].spf>>l[i].number;
sort(l,l+n,cmp1);//将防曬霜從小到大排序
sort(cow,cow+m,cmp);//将牛能承受的最小值從小到大排序
priority_queue<int, vector<int>,greater<int> >q;//存儲牛能承受的防曬霜的最大值
int ans=0,j=0;
for(int i=0; i<n; i++)//枚舉防曬霜
{
while(j<m&&cow[j].begin<=l[i].spf)//如果牛能承受的最小值小于防曬霜的值，将牛能承受的最大值入優先隊列
{
q.push(cow[j].end);
j++;
}
while(!q.empty()&&l[i].number)//從小到大出隊，将防曬霜給牛用，直到這種防曬霜用完。
{
int cnt=q.top();
q.pop();
if(cnt>=l[i].spf)
{
ans++;
l[i].number--;
}
}
}
printf("%d",ans);
//cout<<ans;
}
/*
5 3
3 10
2 5
4 8
4 6
3 5
7 1
9 1
6 2
*/
轉載于:https://www.cnblogs.com/aiguona/p/7218072.html