题目描述

有C头奶牛日光浴，第i头奶牛需要minSPF[i]和maxSPF[i]单位强度之间的强光。每头奶牛在日光浴前必须涂防晒霜，防晒霜有L种，涂上第i种之后，身体接收到的阳光强度就会稳定为SPF[i]，第i种防晒霜有cover[i]瓶。求最多可以满足多少头奶牛进行日光浴。

输入

第一行输入C, L(C, L<=2500)
接下来C行，每行输入miSPF[i]和maxSPF[i]
接下来L行，每行输入SPF[i]和cover[i] (这些数值都在10000以内)

输出

输出答案

样例输入

3 2
3 10
2 5
1 5
6 2
4 1

样例输出

2

思路

优先队列
首先得确定一个贪心策略，在满足minSPF的条件下，尽量把SPF小的防晒霜用在maxSPF小的奶牛身上，因为maxSPF大的奶牛有更大的选择空间。用一个最小堆q维护maxSPF的最小值，可以高效解决问题。

代码

#include <bits/stdc++.h>
using namespace std;

struct node{
    int a,b;
}c[2505],t[2505];

bool cmp(node x,node y){
    return x.a<y.a||(x.a==y.a&&x.b<y.b);
}

priority_queue <int> q;

int ans,n,m;

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i) scanf("%d %d",&c[i].a,&c[i].b);
    for (int i=1;i<=m;++i) scanf("%d %d",&t[i].a,&t[i].b);
    sort(c+1,c+n+1,cmp);
    sort(t+1,t+m+1,cmp);
    int now=1;
    for (int i=1;i<=m;++i){
        while (now<=n && c[now].a<=t[i].a){
            q.push(-c[now].b);
            now++;
        }
        while (t[i].b!=0 && !q.empty()){
            int tmp=-q.top();
            q.pop();
            if (t[i].a<=tmp){
                t[i].b--;
                ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/61/