题意分析

本题要求设计一条高速公路，使得村庄到公路的距离不超过给定值D，并在公路上设置最少的出口，使每个村庄到最近出口的距离不超过D。具体分析如下：

问题建模：

• 高速公路为x轴上的线段[0, L]
• 村庄为平面上的点(x, y)，满足到高速公路的垂直距离 ≤ D
• 出口为高速公路上的点，每个村庄需满足到某个出口的欧氏距离 ≤ D

核心任务： 计算满足条件的最小出口数量。

解题思路

关键观察

1. 投影区间：每个村庄(x, y)在高速公路上对应的可覆盖区间为[x - √(D² - y²), x + √(D² - y²)]，即出口需位于此区间内才能覆盖该村庄。
2. 区间覆盖问题：转化为在x轴上选择最少的点，覆盖所有村庄对应的区间。
3. 贪心策略：按区间右端点排序，每次选择最右侧的点，可最大化覆盖后续区间。

算法步骤

1. 计算区间：对每个村庄，计算其在高速公路上的可覆盖区间。
2. 区间预处理：若区间左端点 < 0，调整为0（高速公路起点）。
3. 区间排序：按右端点升序排列。
4. 贪心选择：从第一个区间开始，每次选择区间的右端点作为出口位置，统计覆盖所有区间所需的最少点数。

标程

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;

struct point {
    double left;
    double right;
} po[100000];

// 按区间右端点升序排序
int cmp(const void *a, const void *b) {
    return (*(point*)a).right < (*(point*)b).right ? -1 : 1;
}

int main() {
    double way_long, dis;  // 公路长度L，距离D
    int n, i, j, k;
    double a, b;  // 村庄坐标(x, y)
    double rec;   // 区间半径√(D² - y²)
    int re;       // 出口数量
    
    while(scanf("%lf%lf%d", &way_long, &dis, &n) != EOF) {
        re = 0;
        for(i = 0; i < n; i++) {
            scanf("%lf%lf", &a, &b);
            rec = sqrt(dis*dis - b*b);  // 计算区间半径
            po[i].left = a - rec;
            po[i].right = a + rec;
            if(po[i].left < 0)  // 区间左端点不小于0
                po[i].left = 0;
        }
        
        qsort(po, n, sizeof(po[0]), cmp);  // 按右端点排序
        
        re = 0;
        i = 0;
        while(i < n) {
            k = i;
            re++;  // 选择当前区间的右端点作为出口
            // 跳过所有被当前出口覆盖的区间
            while(i < n && po[i].left <= po[k].right) i++;
        }
        
        printf("%d\n", re);
    }
    return 0;
}

关键步骤说明

1. 区间计算：

   • 对每个村庄(x, y)，计算其在高速公路上的覆盖区间为[x - √(D² - y²), x + √(D² - y²)]。
   • 若区间左端点小于0，调整为0，确保区间在高速公路范围内。

2. 区间排序：

   • 使用qsort按区间右端点升序排列，确保每次选择的出口能覆盖尽可能多的后续区间。

3. 贪心选择：

   • 初始化出口数量re = 0，遍历所有区间：
     • 选择当前区间的右端点作为出口位置。
     • 跳过所有左端点 ≤ 该出口位置的区间（即被该出口覆盖的区间）。
   • 统计出口总数。

算法正确性证明

1. 最优子结构：每次选择右端点作为出口，可最大化覆盖范围，剩余未覆盖区间仍需最优解。
2. 贪心选择性质：按右端点排序后，选择最右侧的点可覆盖尽可能多的后续区间，保证总出口数最小。

复杂度分析

• 时间复杂度：

  • 计算区间：O(n)
  • 排序：O(n log n)
  • 贪心选择：O(n)
  • 总体：O(n log n)

• 空间复杂度：

  • 存储区间：O(n)

示例解释

输入数据：

100
50
3
2 4
50 10
70 30

计算区间：

• 村庄(2, 4)：√(50² - 4²) ≈ 49.84 → 区间[-47.84, 51.84] → 调整为[0, 51.84]
• 村庄(50, 10)：√(50² - 10²) ≈ 48.99 → 区间[1.01, 98.99]
• 村庄(70, 30)：√(50² - 30²) = 40 → 区间[30, 110] → 调整为[30, 100]

排序后区间：

1. [0, 51.84]
2. [1.01, 98.99]
3. [30, 100]

贪心选择：

• 选择第一个区间右端点51.84，覆盖所有三个区间 → 出口数1。

输出结果：

1