usaco-1.2.1 挤牛奶

题目描述

数轴上有 $N$ 条闭区间 $[s_i, e_i]$ （ $1 \leqslant N \leqslant 5000$ ， $0 \leqslant s_i \leqslant e_i < 10^6$ ）。

求所有区间并集中「至少有一段区间覆盖」的最长连续长度，以及相邻连通块之间「没有任何区间覆盖」的最长连续长度。两个答案按顺序输出一行。

思路

按左端点升序排序后，维护当前极大连通块 $[L,R]$ 。若下一个区间的左端点 $s \leqslant R$ ，则与之重叠或首尾相接，扩展右端 $R = \max(R, e)$ ；否则断开并开启新块。最长块长与相邻块间距的最大值即为答案。

参考代码

Python 版：

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#!/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 02:28
# update_at: 2026-10-04 11:21

import sys


def merge(spans: list[tuple[int, int]]) -> list[list[int]]:
    """把挤奶区间并成互不相邻的极大连通块。

    输入已按左端点升序，所以新区间只可能和「最后一个」块重叠：接得上就并入，
    接不上就开新块，不必回头检查更早的块。
    """
    blocks: list[list[int]] = []
    for start, end in spans:
        if blocks and start <= blocks[-1][1]:          # 重叠、或恰好首尾相接
            blocks[-1][1] = max(blocks[-1][1], end)    # 被包含的区间不能缩短右端
        else:
            blocks.append([start, end])
    return blocks


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    # 每行两个整数：先读左端点，元组排序即按左端点升序
    spans = sorted((next(data), next(data)) for _ in range(n))

    blocks = merge(spans)
    milked = max(end - start for start, end in blocks)  # 有奶：取最长的块
    gaps = (next_start - prev_end                       # 空档只出现在相邻两块之间
            for (_, prev_end), (next_start, _) in zip(blocks, blocks[1:]))
    idle = max(gaps, default=0)                         # 只有一块时不存在空档

    print(milked, idle)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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 09:17
 * update_at: 2026-10-06 09:17
 */

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const ll MAXN = 5005; // 农民数量上限

ll n;
struct Span {
    ll s; // 开始时刻
    ll e; // 结束时刻
} a[MAXN]; // 所有挤奶区间

// 按左端点升序排序
bool cmp_span(const Span &x, const Span &y) {
    return x.s < y.s;
}

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

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i].s >> a[i].e;
    }

    sort(a + 1, a + n + 1, cmp_span);

    // 合并成极大连通块，同时统计答案
    ll block_l = a[1].s;   // 当前块左端点
    ll block_r = a[1].e;   // 当前块右端点
    ll milked = 0;         // 最长有奶时长
    ll idle = 0;           // 最长空档时长

    for (ll i = 2; i <= n; i++) {
        if (a[i].s <= block_r) { // 重叠或首尾相接，属于同一块
            if (a[i].e > block_r) {
                block_r = a[i].e;
            }
        } else { // 断开，结算当前块并开启新块
            milked = max(milked, block_r - block_l);
            idle = max(idle, a[i].s - block_r);
            block_l = a[i].s;
            block_r = a[i].e;
        }
    }
    milked = max(milked, block_r - block_l); // 最后一块也要参与

    cout << milked << " " << idle << "\n";
    return 0;
}

目录

题目描述

思路

参考代码