形式化题目

给定 $C$ 个区间 $[minSPF_i, maxSPF_i]$，以及 $L$ 组「点 + 重数」：第 $j$ 组提供 $cover_j$ 个 取值恰好为 $SPF_j$ 的槽位。一个槽位最多匹配一个区间，一个区间最多匹配一个槽位， 匹配合法当且仅当槽位的值落在区间内。求合法匹配的最大边数，也就是最多有多少个区间能被 互不相同的槽位点中。

正解

思路

朴素做法一：搜索。 一头一头奶牛地枚举它涂哪一瓶防晒霜，回溯搜索。分支因子是 $L$， 深度是 $C$，规模随 $C$ 指数增长；$C$ 最大 2500，完全不可行。

朴素做法二：二分图最大匹配。 左边 $C$ 头奶牛、右边 $L$ 种防晒霜（容量 $cover_j$）， 相容就连边，跑最大流。这是多项式的，但边数最坏 $C \times L \approx 6.25 \times 10^6$， 实现和常数都不友好。所以要想：能不能只看局部信息就决定每一瓶防晒霜给谁？

关键观察：在同一个 SPF 上，奶牛之间只有「谁更急」的区别。 把防晒霜按 $SPF$ 从小到大发放。当处理到某个值 $s$ 时，所有 $minSPF \leqslant s$ 的奶牛 都已经「解锁」——它们都能接受 $s$ 以及之后更大的值。此时它们之间的区别只剩下 $maxSPF$：

$maxSPF$ 越小的奶牛，未来可用的 SPF 集合越小。

用样例验证这个直觉。先把三头奶牛按 minSPF 升序记为 $u_1=(1,5)$、$u_2=(2,5)$、$u_3=(3,10)$， 再把区间与防晒霜画在 SPF 轴上（# 表示该强度落在区间内）：

1
2
3
4
5强度        1    2    3    4    5    6    7    8    9    10
u1(1,5)     #    #    #    #    #    .    .    .    .    .
u2(2,5)     .    #    #    #    #    .    .    .    .    .
u3(3,10)    .    .    #    #    #    #    #    #    #    #
防晒霜      .    .    .    4    .    6    .    .    .    .

观察这张图：SPF=4 有三个候选（$u_1,u_2,u_3$），SPF=6 只剩一个候选（$u_3$）。 如果贪心准则选错，把 SPF=4 的那一瓶给了 $u_3$，6 的两瓶就全部浪费了。 所以 $maxSPF$ 小的必须先满足：它现在不要，以后就更没有机会。

于是得到贪心：按 SPF 升序扫描每一瓶防晒霜，每瓶都优先给「能接受它且 $maxSPF$ 最小」的那头奶牛。

如何高效实现。 直接按上面这句话写，每一瓶都要在全体奶牛里找一遍候选，是 $O(CL)$。 利用 SPF 递增这个结构可以降到 $O((C+L)\log C)$：

1. 奶牛按 $minSPF$ 升序排序，防晒霜按 $SPF$ 升序排序。
2. 用一个下标 next_cow 顺序推进：扫到值为 $s$ 的防晒霜时，把 $minSPF \leqslant s$ 的奶牛 （也就是刚刚「解锁」的那一段）的 $maxSPF$ 依次压入小根堆。因为 $s$ 单调递增， 每头奶牛只会入堆一次，指针也只会前进一次。
3. 堆顶是待选池中 $maxSPF$ 最小的奶牛。先把堆顶所有 $maxSPF < s$ 的奶牛弹出： 它们连当前这瓶都用不了，之后更大的 $SPF$ 更用不了，可以永久放弃。
4. 若这瓶防晒霜还有余量且堆非空，就反复「弹出堆顶、答案 +1、余量 −1」—— 堆顶正是「最急」的那头。

第 3、4 步的顺序不能颠倒：必须先把过期奶牛清走，才能保证喂出去的都是合法匹配。

代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45#!/usr/bin/env python3
# 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-10-01 10:26
# update_at: 2026-10-01 10:26

import sys
from heapq import heappop, heappush


def max_satisfied(cows: list[tuple[int, int]], bottles: list[tuple[int, int]]) -> int:
    """按 SPF 从小到大发放防晒霜，每个强度下优先喂给 maxSPF 最小（最快过期）的奶牛。

    左端点不足的奶牛晚点才进入待选池，所以扫描 SPF 时把它们按 minSPF 逐个入堆，
    堆按 maxSPF 排序：堆顶一旦连当前 SPF 都够不到，就再也用不上任何防晒霜了。
    """
    pending: list[int] = []  # 待选奶牛的 maxSPF，堆顶是其中最急的一头
    next_cow = 0             # 下一头等待进入待选池的奶牛下标
    ans = 0
    for spf, cover in bottles:
        while next_cow < len(cows) and cows[next_cow][0] <= spf:  # minSPF 已到，可以接受这瓶
            heappush(pending, cows[next_cow][1])
            next_cow += 1
        while pending and pending[0] < spf:  # 堆顶这头牛的 maxSPF 已经过期，彻底放弃
            heappop(pending)
        while cover > 0 and pending:  # 同强度的每一瓶都给当前最快过期的奶牛
            heappop(pending)
            cover -= 1
            ans += 1
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    C, L = next(data), next(data)

    cows = sorted((next(data), next(data)) for _ in range(C))     # 按 minSPF 升序，配合扫描依次入堆
    bottles = sorted((next(data), next(data)) for _ in range(L))  # 按 SPF 升序依次发放

    print(max_satisfied(cows, bottles))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-10-06 14:15
 * update_at: 2026-10-06 14:15
 */

// main.cpp：把奶牛看成 SPF 轴上的区间、防晒霜看成带重数的点，求最大匹配数。
// 做法：防晒霜按 SPF 升序发放，用小根堆维护待选奶牛，优先满足 maxSPF 最小（最快过期）的奶牛。

#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>

typedef long long ll;

const int MAXN = 2505;

int C, L;
std::pair<ll, ll> cow[MAXN];   // cow[i] = {minSPF, maxSPF}，按 minSPF 升序排序
std::pair<ll, ll> bottle[MAXN]; // bottle[j] = {SPF, cover}，按 SPF 升序排序

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

    std::cin >> C >> L;
    for (int i = 0; i < C; i++)
        std::cin >> cow[i].first >> cow[i].second;
    for (int j = 0; j < L; j++)
        std::cin >> bottle[j].first >> bottle[j].second;

    // 奶牛按 minSPF 升序：扫到 SPF=s 时，minSPF<=s 的奶牛刚好全部解锁
    std::sort(cow, cow + C);
    // 防晒霜按 SPF 升序依次发放
    std::sort(bottle, bottle + L);

    // 小根堆存待选奶牛的 maxSPF：堆顶是可行集合最小（最急）的那头
    std::priority_queue<ll, std::vector<ll>, std::greater<ll> > pending;
    int next_cow = 0; // 下一头等待入堆的奶牛下标，只前进不后退
    ll ans = 0;

    for (int j = 0; j < L; j++) {
        ll spf = bottle[j].first;
        ll cover = bottle[j].second;

        // 把 minSPF <= s 的奶牛压入堆，每头牛只入堆一次
        while (next_cow < C && cow[next_cow].first <= spf) {
            pending.push(cow[next_cow].second);
            next_cow++;
        }
        // 先清掉已经过期的奶牛：maxSPF < s 连这瓶都接受不了，以后更没机会
        while (!pending.empty() && pending.top() < spf)
            pending.pop();
        // 每瓶优先发给最急（maxSPF 最小）的奶牛
        while (cover > 0 && !pending.empty()) {
            pending.pop();
            cover--;
            ans++;
        }
    }

    std::cout << ans << std::endl;
    return 0;
}

复杂度

空间 $O(C + L)$：奶牛、防晒霜、堆各一份。最大数据 $C = L = 2500$ 实测约 0.02 s、峰值 15 MB， 远低于 1000 ms / 128 MB。

总结

本题的核心是把「区间与点的匹配」放到时间轴上扫描：

1. 模型：奶牛是区间 $[minSPF, maxSPF]$，防晒霜是 SPF 轴上的点（带重数），求最大匹配数。
2. 贪心准则：按 SPF 升序发放，每瓶优先给能接受它的、$maxSPF$ 最小的奶牛 —— 因为在同一时刻所有候选的 $minSPF$ 都已满足，$maxSPF$ 小者的可行集合是别人的子集，最急。
3. 实现：minSPF 升序的指针 + maxSPF 的小根堆，把「找最急的候选」从 $O(C)$ 降到 $O(\log C)$。

交换论证保证了贪心的正确性：若最优解把当前最急的奶牛 $u$ 安排到了更晚的 $s'$， 而把当前 SPF $s$ 给了牛 $v$，则由 $maxSPF_u \leqslant maxSPF_v$ 与 $minSPF_v \leqslant s \leqslant s'$ 可知把两者的防晒霜互换后方案依然合法，说明贪心选择总能被某个最优解采用。

图示解析

下面这张表把样例 $C=3, L=2$ 的贪心过程逐步摊开，展示待选池、堆顶与答案的变化。

样例的输入是：奶牛区间 $(3,10)$、$(2,5)$、$(1,5)$；防晒霜 SPF=6 有 2 瓶、SPF=4 有 1 瓶。 排序后按 $minSPF$ 升序记为 $u_1=(1,5)$、$u_2=(2,5)$、$u_3=(3,10)$， 防晒霜按 $SPF$ 升序为 (4, 1)、(6, 2)。

得到答案 2，与样例一致。

观察重点有三个：

1. 第 1 步的候选是全部三头牛，但算法选择 $u_1$，因为它的 $maxSPF=5$ 最小 —— 最急的先喂。
2. 第 2 步开始时 $u_2$ 的 $maxSPF=5 \lt 6$ 被淘汰，这就是「先弹出过期奶牛」这一步的作用： 如果没有它，SPF=6 就会错喂给 $u_2$，而 $u_3$ 也就再没有机会了。
3. 若第 1 步改把 SPF=4 给 $u_3$（违反贪心准则），第 2 步的 SPF=6 两瓶就无人可用 （$u_1, u_2$ 的 $maxSPF$ 都是 5），答案从 2 掉到 1 —— 这正是「$maxSPF$ 小者的可行集合是别人子集、 子集必须先满足」的代价。