题目链接

算法竞赛进阶指南-24.防晒

本题是一道区间问题，区间问题往往具有贪心策略，并与排序相关。

Method : 贪心

难点在于这个问题：为什么不能将奶牛的单位强度按照minSPF从小到大排序,然后防晒霜也按照从小到大排序,将最小的先和最小的进行匹配呢？

[1, 5]和[2, 3]和spfs[1] = 1, spfs[2] = 1. 这个包含关系在排序后始终要优先考虑区间[2, 3]

不管是按左端点排序还是按右端点排序，始终要注意一点:

先考虑的区间不能完全包含后考虑的区间

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

using namespace std;

typedef pair<int, int> PII;

const int C = 2500 + 7;
const int L = 2500 + 7;

int c, l;
vector<PII> cows;
map<int, int> spfs;

int main() {
    cin >> c >> l;
    for (int i = 0; i < c; i ++) {
        int min_spf, max_spf;
        scanf("%d %d", &min_spf, &max_spf);
        cows.push_back({min_spf, max_spf});
    }
    for (int i = 0; i < l; i ++) {
        int spf,  cover;
        scanf("%d %d", &spf, &cover);
        spfs[spf] += cover;
    }
    
    int res = 0;
    sort(cows.begin(), cows.end());
    for (int i = cows.size() - 1; i >= 0; i --) {
        auto spf = spfs.upper_bound(cows[i].second);
        if (spf == spfs.begin()) continue; // 对upper_bound()函数检查边界
        else spf = prev(spf);
        if (spf->first >= cows[i].first) {
            res ++;
            spf->second --;
            if (spf->second == 0) {
                spfs.erase(spf);
            }
        }
    }
    
    cout << res << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度${O(nlogn)}$， 第一步快速排序sort的时间复杂度 是$O(nlogn)$，第二步$n$次循环中每次二分$O(logn)$，合计${O(nlogn)}$。

• 空间复杂度${O(n)}$，spfs的map和cows数组长度均为$n$。