Sunscreen_牛客博客

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
输入

输出

题解：
每个牛所需要的的乳液都在它规定的范围内
我们可以将乳液从小到大排序
将牛的最小需求从小到大排
我们先将牛的最小需求根乳液比较，如果乳液大于最小需求，就存入优先队列里，（优先队列从小到大排），然后再一次比较当前乳液与队列里牛的最大需求，（凡是在队列里的牛，最小需求一定小于乳液，所以只需比较最大需求是否大于）
队列为什么是从小到大排，因为最大需求越小，说明它要达成的条件越苛刻，先把难搞的搞定剩下的好说
代码：

#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;
}