《算法竞赛进阶指南》 Sunscreen--题解

题目描述
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

别处的翻译：
题目描述
有C头(1 ≤ C ≤ 2500)奶牛进行日光浴，第i头奶牛需要minSPF[i]到maxSPF[i](1 ≤ minSPFi ≤ 1,000; minSPFi ≤ maxSPFi ≤ 1,000)单位强度之间的阳光。
每头奶牛在日光浴前必须涂防晒霜，防晒霜有L种(1 ≤ L ≤ 2500)，涂上第i种之后，身体接收到的阳光强度就会稳定为SPF[i](1 ≤ SPFi ≤ 1,000)，第i种防晒霜有cover[i]瓶。
求最多可以满足多少头奶牛进行日光浴。

输入描述
第一行输入整数C和L。
接下来的C行，按次序每行输入一头牛的minSPF和maxSPF值,即第i行输入minSPF[i]和maxSPF[i]。
再接下来的L行，按次序每行输入一种防晒霜的SPF和cover值,即第i行输入SPF[i]和cover[i]。
每行的数据之间用空格隔开。

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

贪心算法介绍：
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关

算法流程
1.按每头奶牛的minSPF从大到小排序，然后按照顺序考虑每一头奶牛。
2.对于每一头奶牛，扫描一遍所能使用的防晒霜，并在所有适用的防晒霜中选择SPF值最大的防晒霜。

总时间复杂度：
O(nlogn)

完整C++版AC代码：

/*
    把所有奶牛和防晒霜分别看成两个集合中的点如果一头奶牛可以使用某个防晒霜，
    则在两个点之间连一条边，那么问题就变成二分图求最大匹配。
*/

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 2501;
PII cows[N];//表示奶牛minSPF[i]和maxSPF[i]
int C, L;

int main() {
    cin >> C >> L;
    map<int, int> spfs;

    for (int i = 0; i < C; i++) cin >> cows[i].first >> cows[i].second;
    sort(cows, cows + C);
    for (int i = 0; i < L; i++) {
        int spf, cover;//spf表示防晒霜的在区间上的点，cover是防晒霜的数量
        cin >> spf >> cover;
        spfs[spf] += cover;//这里要写 +=，因为数据中存在spf值相同的防晒霜
    }
    int ans = 0;
    spfs[0] = spfs[1001] = C;//哨兵节点
    for (int i = C - 1; i >= 0; i--)
    {
        auto it = spfs.upper_bound(cows[i].second);//在所有防晒霜中找到第一个大于第i只牛所适用的防晒霜
        it--;//找到第一个小于等于第i只牛所适用的防晒霜，也就是第i头奶牛所有适用的防晒霜中SPF值最大的防晒霜
        if (it->first >= cows[i].first) {
            ans++;
            if (--it->second == 0) {
                spfs.erase(it);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

(以前学这道题时是看yxc大佬的视频的，所以代码以及思路和大佬的差不多（几乎）相同)
附yxc大佬的视频讲解：https://www.bilibili.com/video/av44795052