[USACO07NOV] Sunscreen G

GitHub跳转原题关系图返回列表

按 SPF 升序扫描防晒霜，用小根堆优先匹配 maxSPF 最小、最快过期的奶牛。

OJ: luogu

题目 ID: P2887

难度:普及/提高-

标签:贪心堆区间覆盖排序

日期: 2026-06-22 21:13

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

每头奶牛能接受一个 SPF 区间 [minSPF,maxSPF]。

每种防晒霜有固定 SPF 和若干瓶。每瓶只能给一头奶牛用。

求最多能满足多少头奶牛。

思路

先看一个可以直接验证想法的朴素解：

cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

struct Cow {
    int min_spf;
    int max_spf;
};

int c, l;
Cow cows[MAXN];
vector<int> bottles;
vector<int> graph_edges[MAXN];
int match_to[MAXN];
bool vis[MAXN];

bool dfs_match(int u) {
    for (int i = 0; i < (int)graph_edges[u].size(); i++) {
        int v = graph_edges[u][i];
        if (vis[v]) {
            continue;
        }
        vis[v] = true;
        if (match_to[v] == 0 || dfs_match(match_to[v])) {
            match_to[v] = u;
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> c >> l;
    for (int i = 1; i <= c; i++) {
        cin >> cows[i].min_spf >> cows[i].max_spf;
    }
    for (int i = 1; i <= l; i++) {
        int spf, cover;
        cin >> spf >> cover;
        for (int j = 0; j < cover; j++) {
            bottles.push_back(spf);
        }
    }

    for (int i = 1; i <= c; i++) {
        for (int j = 0; j < (int)bottles.size(); j++) {
            if (cows[i].min_spf <= bottles[j] && bottles[j] <= cows[i].max_spf) {
                graph_edges[i].push_back(j + 1);
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= c; i++) {
        memset(vis, false, sizeof(vis));
        if (dfs_match(i)) {
            ans++;
        }
    }

    cout << ans << '\n';
    return 0;
}

暴力可以把每瓶防晒霜展开成一个点，再跑二分图最大匹配。正解使用更直接的贪心。

按 SPF 从小到大处理防晒霜。当前 SPF 下，所有 minSPF <= SPF 的奶牛才可能使用它，把这些奶牛加入候选集合。

候选集合中，如果 maxSPF < SPF，说明这头奶牛已经无法使用当前以及后续更大的 SPF，直接丢弃。

剩下的奶牛里，应该优先满足 maxSPF 最小的奶牛。因为它最容易在后面过期；如果当前不给它用，未来只会更难。

所以用小根堆维护候选奶牛的 maxSPF，每瓶防晒霜匹配堆顶。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2505;

struct Cow {
    int min_spf;
    int max_spf;
};

struct Lotion {
    int spf;
    int cover;
};

int c, l;
Cow cows[MAXN];
Lotion lotions[MAXN];

bool cmp_cow_min(const Cow &a, const Cow &b) {
    if (a.min_spf != b.min_spf) {
        return a.min_spf < b.min_spf;
    }
    return a.max_spf < b.max_spf;
}

bool cmp_lotion(const Lotion &a, const Lotion &b) {
    return a.spf < b.spf;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> c >> l;
    for (int i = 1; i <= c; i++) {
        cin >> cows[i].min_spf >> cows[i].max_spf;
    }
    for (int i = 1; i <= l; i++) {
        cin >> lotions[i].spf >> lotions[i].cover;
    }

    sort(cows + 1, cows + c + 1, cmp_cow_min);
    sort(lotions + 1, lotions + l + 1, cmp_lotion);

    priority_queue<int, vector<int>, greater<int> > pq;
    int ptr = 1;
    int ans = 0;

    for (int i = 1; i <= l; i++) {
        int spf = lotions[i].spf;
        while (ptr <= c && cows[ptr].min_spf <= spf) {
            pq.push(cows[ptr].max_spf);
            ptr++;
        }

        int cnt = lotions[i].cover;
        while (cnt > 0 && !pq.empty()) {
            int max_spf = pq.top();
            pq.pop();
            if (max_spf < spf) {
                continue;
            }
            ans++;
            cnt--;
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

排序和堆操作总复杂度约为：

text
O((C+L+总瓶数) log C)

空间复杂度为 O(C+L)O(C+L)。

总结

本题的贪心重点是“谁最急”。

按 SPF 递增扫描时，maxSPF 最小的奶牛最容易失去机会，所以每次都优先满足它。