「一本通 1.1 例 3」喷水装置

题目描述

长 $L$ 、宽 $W$ 的草坪中心线上装 $n$ 个喷头，给出每个喷头离左端的位置和浇灌半径。求同时浇灌整块草坪最少需打开几个喷头；无法浇灌输出 $-1$ 。 $n \leqslant 15000$ ，多组数据。

思路

把能覆盖到草坪上下两边的喷头按勾股定理转成中心线上的有效区间 $[pos-reach,\ pos+reach]$ ，半径不足半宽的喷头直接丢弃。区间按左端点排序后，从 $0$ 出发反复在所有左端不超过当前覆盖点的区间里选右端最远者，直到覆盖 $L$ 或无法推进，贪心选中的区间数即答案。

参考代码

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
43
44
45
46
47
48
49
50
51
52#!/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-07-05 21:47
# update_at: 2026-07-05 21:47

import sys
from math import sqrt


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        n, L, W = next(data), next(data), next(data)
        half = W / 2

        # 每个喷头映射成中心线上的有效区间 [l, r]：半径盖不到半宽的喷头无效
        spans: list[tuple[float, float]] = []
        for _ in range(n):
            pos, radius = next(data), next(data)
            ok = radius > half                      # radius == half 时区间退化为点，盖不了长度
            if ok:
                reach = sqrt(radius * radius - half * half)  # 有效覆盖半长（勾股定理）
                spans.append((pos - reach, pos + reach))

        # 经典区间覆盖贪心：区间按左端排序，从起点 cur 出发，反复取
        # "左端不超过 cur 的区间中右端最远者"，跳不到就输出 -1
        spans.sort()
        count, cur, i = 0, 0.0, 0
        n = len(spans)
        while cur < L:
            # 单轮扩展：左端 <= cur 的候选里选最远右端；i 跳过上一轮已完全落在 cur 左侧的区间
            far, j = cur, i
            while j < n and spans[j][0] <= cur:
                far = max(far, spans[j][1])
                j += 1
            if j == i or far <= cur:              # 没有区间能从 cur 继续向前推进
                break
            count += 1
            cur, i = far, j

        out.append(str(count if cur >= L else -1))

    print('\n'.join(out))


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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83/**
 * 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-05 23:22
 * update_at: 2026-10-05 23:22
 */

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 15005;  // 最多喷头数

int n;                   // 每组喷头数量
ll L, W;                 // 草坪长、宽

double segL[MAXN];       // 每个有效喷头的左端点
double segR[MAXN];       // 每个有效喷头的右端点

// 对有效区间按左端点升序排序（指针扫过时只需左端有序）
bool cmp_seg(int a, int b) {
    return segL[a] < segL[b];
}

// 单组数据求解：最少喷头数，无法覆盖返回 -1
int solve_one() {
    if (L == 0) return 0;  // 无需覆盖

    int m = 0;             // 有效喷头数量
    double half = W / 2.0; // 半宽

    for (int i = 0; i < n; i++) {
        ll pos, r;
        scanf("%lld %lld", &pos, &r);
        double dr = r;  // 避免后续强制转换
        // 半径不超过半宽则圆够不到上下边，此喷头无效
        if (dr <= half) continue;
        double reach = sqrt(dr * dr - half * half);  // 中心线有效半长
        segL[m] = pos - reach;
        segR[m] = pos + reach;
        m++;
    }

    // idx 为区间按左端点排序后的下标
    int idx[MAXN];
    for (int i = 0; i < m; i++) idx[i] = i;
    sort(idx, idx + m, cmp_seg);

    double cur = 0.0;      // 当前已覆盖到的位置
    int i = 0;             // 排序后区间的扫描指针
    int ans = 0;

    while (cur < L) {
        double far = cur;  // 本步能到达的最远右端
        int j = i;
        // 所有左端不超过 cur 的区间中，取右端最远的
        while (j < m && segL[idx[j]] <= cur + 1e-9) {
            if (segR[idx[j]] > far) far = segR[idx[j]];
            j++;
        }
        // 没有区间能继续推进
        if (j == i || far <= cur + 1e-9) return -1;
        cur = far;
        i = j;
        ans++;
    }

    return ans;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %lld %lld", &n, &L, &W);
        printf("%d\n", solve_one());
    }
    return 0;
}

「一本通 1.1 例 3」喷水装置

目录

题目描述

思路

参考代码