来源：牛客网
Sunscreen
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
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: 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 输出描述: A single line
with an integer that is the maximum number of cows that can be
protected while tanning
示例1
输入
3 2
3 10
2 5
1 5
6 2
4 1
输出
2
题解：
每个牛所需要的的乳液都在它规定的范围内
我们可以将乳液从小到大排序
将牛的最小需求从小到大排
我们先将牛的最小需求根乳液比较，如果乳液大于最小需求，就存入优先队列里，（优先队列从小到大排），然后再一次比较当前乳液与队列里牛的最大需求，（凡是在队列里的牛，最小需求一定小于乳液，所以只需比较最大需求是否大于）
队列为什么是从小到大排，因为最大需求越小，说明它要达成的条件越苛刻，先把难搞的搞定剩下的好说
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn=2520;
int cnt=1, sum;
struct node{int first;int second;
}cow[maxn];
struct node1{int num;int SPF;
}b[maxn];
bool cmp1(node a,node b) {return a.second < b.second;
}
bool cmp2(node1 a,node1 b) {return a.SPF < b.SPF;
}template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
priority_queue<int, vector<int>, greater<int> > q;
int main() {int c, l;cin >> c >> l;for (int i = 1; i <= c; i++) read(cow[i].second),read(cow[i].first) ;for (int i = 1; i <=l; i++)read(b[i].SPF),read(b[i].num);sort(cow+1, cow + c +1, cmp1);sort(b+1, b + l +1, cmp2);for (int i = 1; i <= l; i++){while ( cow[cnt].second <= b[i].SPF&&cnt <= c) {q.push(cow[cnt].first);cnt++;}while (!q.empty() && b[i].num>=0) {int x; x = q.top();q.pop();if (x >= b[i].SPF) {b[i].num--;sum++;}}}cout << sum << endl;return 0;
}