AcWing：110. 防晒（贪心）

2022-09-29 12:24:43

有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]。

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

输出格式

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

数据范围

输入样例：

输出样例：

算法：贪心

题解：结构体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 = 2507;

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 = 1; i <= n; i++) {
        scanf("%d %d", &a[i].min_spf, &a[i].max_spf);
    }
    for(int i = 1; i <= m; i++) {
        scanf("%d %d", &b[i].spf, &b[i].cover);
    }
    sort(a + 1, a + n + 1, cmp1);
    sort(b + 1, b + m + 1, cmp2);
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(b[j].cover > 0 && a[i].min_spf <= b[j].spf && b[j].spf <= a[i].max_spf) {
                b[j].cover--;
                ans++;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;   
}