喷水装置

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1402 字
喷头覆盖转区间后做最少区间覆盖
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1424
// 题意：长 L 宽 W 的草坪中心线上有 n 个圆形喷头，给出位置和半径，求覆盖整条草坪最少要开几个喷头，无解输出 -1。
// 思路：把每个喷头转化成它能覆盖的横向区间，再做区间覆盖贪心。
// 1. 半径 r <= W / 2 的喷头覆盖不到草坪上下边缘，直接丢弃。
// 2. 有效喷头的覆盖区间为 [x - d, x + d]，其中 d = sqrt(r * r - (W / 2)^2)。
// 3. 按左端点排序，每次在左端点不超过当前已覆盖位置的喷头里，选右端点最远的那个。
// 复杂度：O(n log n) 时间 / O(n) 空间
// 易错点：喷头的覆盖宽度是 2 * sqrt(r^2 - (W/2)^2)，别忘了先减掉半个宽度 W/2。
// 易错点：某一轮选不出任何能向右推进的喷头时要立刻判定无解，否则会死循环。
#include <bits/stdc++.h>
using namespace std;
int main(){
    int T;
    if(!(cin >> T)) return 0;
    while(T--){
        int n;
        double L, W;
        cin >> n >> L >> W;
        vector<pair<double, double>> seg;
        for(int i = 0; i < n; i++){
            double x, r;
            cin >> x >> r;
            if(r <= W / 2) continue;
            double d = sqrt(r * r - (W / 2) * (W / 2));
            seg.push_back({x - d, x + d});
        }
        sort(seg.begin(), seg.end());
        double cur = 0;
        int ans = 0;
        int i = 0;
        while(cur < L){
            double far = cur;
            int j = i;
            while(j < (int)seg.size() && seg[j].first <= cur){
                far = max(far, seg[j].second);
                j++;
            }
            if(far <= cur){
                ans = -1;
                break;
            }
            cur = far;
            i = j;
            ans++;
        }
        cout << ans << "\n";
    }
    return 0;
}
喷水装置

正文

一本通·提高篇的其它内容
