[USACO07NOV] Sunscreen G

题意

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

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

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

思路

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

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68// 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，每瓶防晒霜匹配堆顶。

这份贪心还有等价的“从奶牛出发”的写法：把处理对象换成奶牛，按 maxSPF 从小到大排序；每头牛在还有货、且 SPF 落在自己区间内的防晒霜里，取 SPF 最小的那瓶。两种写法贯彻的是同一句话——上限最紧的奶牛最急。区别只在谁在外层扫描：堆版按 SPF 递增扫描防晒霜，天然做到“把最小的可行 SPF 留给当前牛”；从奶牛出发的版本把这个顺序显式写出来。

样例推演

样例中有 3 头奶牛 [3,10]、[2,5]、[1,5]，防晒霜 SPF6×2、SPF4×1。按 maxSPF 升序依次处理：

顺序	奶牛 `[minSPF,maxSPF]`	选中的防晒霜	剩余瓶数 `SPF4 / SPF6`	累计答案
1	`[2,5]`	`SPF4`	0 / 2	1
2	`[1,5]`	无可用	0 / 2	1
3	`[3,10]`	`SPF6`	0 / 1	2

第 1 头牛用掉 SPF4 后，第 3 头牛还能用 SPF6，所以最终能同时满足两头牛。如果第 1 头牛先把 SPF6 抢走，[1,5] 和 [2,5] 都用不上它，答案反而只剩 1。

Python 知识

sys.stdin.buffer.read().split() 一次读入全部整数，再用 iter(...) 和 next(...) 顺序取用，比逐行 input() 更省事也更稳。
防晒霜存成 [spf, cover] 这样的可变列表时，item[1] -= 1 才会写回原列表；写成 for a, cnt in lofs 再改 cnt 只改到局部变量，cover 不会减少。
lofs.sort(key=lambda x: x[0]) 按 SPF 升序排列，于是“取第一瓶可用的”就等价于“取 SPF 最小的一瓶”。

代码

主解使用小根堆：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71#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;
}

另一种贪心写法（C++）

从奶牛出发，按 maxSPF 升序处理，内层顺序扫描防晒霜，取 SPF 最小的可用瓶。时间复杂度 $O(C \cdot L)$ ，在 $C,L \leqslant 2500$ 时约 $6 \times 10^6$ 次判断，同样能通过。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-27 15:59
 * update_at: 2026-09-27 15:59
 */
// main2.cpp：O(C*L) 双重循环贪心，和 main.cpp 的优先队列做法形成对照。
// 思路：奶牛按 maxSPF 从小到大处理，每头牛在所有还有货的防晒霜里取 SPF 最小的那瓶。
// 为什么这样贪心安全：maxSPF 小的牛可选范围最窄，先满足它；而给它最小的可行 SPF，
// 等于把更大的 SPF 让给上限更大的牛，不会让答案变差。

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

const int MAXN = 2505;

int C, L;

struct Cow {
    int min_spf;
    int max_spf;
};

struct Lotion {
    int spf;
    int cover;
};

Cow cows[MAXN];       // 奶牛的 minSPF / maxSPF
Lotion lotions[MAXN]; // 防晒霜的 SPF 和剩余瓶数

// 奶牛按 maxSPF 升序，maxSPF 相同时按 minSPF 升序，保证处理顺序确定。
bool cmp_cow(const Cow &a, const Cow &b) {
    if (a.max_spf != b.max_spf) {
        return a.max_spf < b.max_spf;
    }
    return a.min_spf < b.min_spf;
}

// 防晒霜按 SPF 升序，方便从前往后找第一瓶可用的（即 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);
    sort(lotions + 1, lotions + L + 1, cmp_lotion);

    int ans = 0;
    for (int i = 1; i <= C; i++) {
        int lo = cows[i].min_spf;
        int hi = cows[i].max_spf;
        // 找 SPF 最小的可用防晒霜：它最难被别的牛用掉，优先分给当前上限最小的牛。
        for (int j = 1; j <= L; j++) {
            if (lotions[j].cover > 0 && lo <= lotions[j].spf && lotions[j].spf <= hi) {
                lotions[j].cover--;
                ans++;
                break;
            }
        }
    }

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

Python 版本

和上面从奶牛出发的 C++ 版本是同一个算法。

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30import sys

tokens = iter(map(int, sys.stdin.buffer.read().split()))
C = next(tokens)
L = next(tokens)
cows = [(next(tokens) ,next(tokens))for _ in range(C)]
lofs = [[next(tokens) ,next(tokens)]for _ in range(L)]

# print(cows)
# print(lofs)


# cows 按第二个值排序
cows.sort(key=lambda x: x[1])
# lofs 按第二个值排序
lofs.sort(key=lambda x: x[0])

def pick_one(l,r):
    for item in lofs:
        if l <= item[0] <= r and item[1] > 0:
            item[1] -= 1
            return 1
    return 0

ans = 0;
for l,r in cows:
    # print(l,r)
    ans+= pick_one(l,r)

print(ans)

复杂度

堆版对奶牛和防晒霜各排序一次，每个候选奶牛进出堆一次，总复杂度约为：

text

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

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

从奶牛出发的版本排序后是双重循环，时间为 $O(C \cdot L)$ ，空间同样是 $O(C+L)$ 。

总结

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

按 SPF 递增扫描时，maxSPF 最小的奶牛最容易失去机会，所以每次都优先满足它；换成从奶牛出发的写法，就是按 maxSPF 升序处理、每次分给它最小的可行 SPF。两种写法是同一件事的两种视角。