题目描述

有C头奶牛进行日光浴，第i头奶牛需要minSPF[i]到maxSPF[i]单位强度之间的阳光。

每头奶牛在日光浴前必须涂防晒霜，防晒霜有L种，涂上第i种之后，身体接收到的阳光强度就会稳定为SPF[i]，第i种防晒霜有cover[i]瓶。

求最多可以满足多少头奶牛进行日光浴。

输入格式
第一行输入整数C和L。

接下来的C行，按次序每行输入一头牛的minSPF和maxSPF值,即第i行输入minSPF[i]和maxSPF[i]。

再接下来的L行，按次序每行输入一种防晒霜的SPF和cover值,即第i行输入SPF[i]和cover[i]。

每行的数据之间用空格隔开。

输出格式
输出一个整数，代表最多可以满足奶牛日光浴的奶牛数目。

数据范围
1≤C,L≤25001≤C,L≤2500
1≤minSPF≤maxSPF≤10001≤minSPF≤maxSPF≤1000
1≤SPF≤1000
样例
输入样例：
3 2
3 10
2 5
1 5
6 2
4 1
输出样例：
2

我的代码采用的是第二种方法
1，题目要求满足奶牛数量要最多，我们可以对minSPF[i]进行从小到大排序，这样固定了每头奶牛的最小值，每两头奶牛的光照强度可能有重合部分，我们先从光照最大那头牛开始，如果有多只防晒霜在符合这头奶牛，我们在符合这个范围内护肤霜选择光照最大的护肤霜，这样就避免了先选择重合部分护肤霜，而让下面的奶牛没有合适的可选，从而达到最优选择。
2，当然，也可以对maxSPF[i]从小到大排序，固定住最大值，此时，就要从光照最小奶牛开始，注意，选择的护肤霜要尽可能的接近最小光照

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int N=3500;
typedef pair<int,int>Pll;
Pll a[N];
map <int,int>b;//存储护肤霜的强度和瓶数
int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>a[i].second>>a[i].first;//second存储最小值，first存最大值
    sort(a,a+n);//按最大值从小到达排序
    for(int i=0,x,y;i<m;i++)
    {
        cin>>x>>y;
        b[x]+=y;//护肤霜种类可能相同
    }
    int ans=0;
       for(int i=0;i<n;i++)
        for(auto it=b.begin();it!=b.end();it++)//从小到大使用map，map数组中first存护肤霜强度，second为瓶数
        if(it->first>=a[i].second&&it->first<=a[i].first&&it->second)//a[i].second为最小值，a[i].first为最大值
          {
              --it->second;
              ans++;
              break; 
          } //优先选择靠近最小值的护肤霜
        cout<<ans<<endl;
        return 0;
}