AcWing：110. 防晒（贪心）

有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≤10001≤SPF≤1000

输入样例：

输出样例：

算法：贪心

题解：结构体a按照min_spf递减排序，结构体b按照spf递减排序，这是为什么呢？因为加入当前奶牛i可以用任意两瓶防晒霜x，y（x，y在 [ a[i].min_spf, a[i].max_spf ] 的范围内）下面的奶牛对于x，y的使用就可能出现三种情况：第一，x和y都能用。第二，x和y都不能用。第三，x能用，y不能用。所以我们就需要优先使用比较大的那个spf。

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn = ;

struct spf {

    int min_spf, max_spf;

}a[maxn];

struct node_spf {

    int spf, cover;

}b[maxn];

bool cmp1(spf a, spf b) {

    if(a.min_spf == b.min_spf) {

        return a.max_spf > b.max_spf;

    }

    return a.min_spf > b.min_spf;

}

bool cmp2(node_spf a, node_spf b) {

    return a.spf > b.spf;

}

int main() {

    int n, m;

    scanf("%d %d", &n, &m);

    for(int i = ; i <= n; i++) {

        scanf("%d %d", &a[i].min_spf, &a[i].max_spf);

    }

    for(int i = ; i <= m; i++) {

        scanf("%d %d", &b[i].spf, &b[i].cover);

    }

    sort(a + , a + n + , cmp1);

    sort(b + , b + m + , cmp2);

    int ans = ;

    for(int i = ; i <= n; i++) {

        for(int j = ; j <= m; j++) {

            if(b[j].cover >  && a[i].min_spf <= b[j].spf && b[j].spf <= a[i].max_spf) {

                b[j].cover--;

                ans++;

                break;

            }

        }

    }

    cout << ans << endl;

    return ;

}

巴特西