最少标记点问题：贪心算法解析

最少标记点问题：贪心算法解析

问题描述

在一条直线上有n个点，其中第i个点的位置是Xi。我们需要从这些点中选择若干个进行标记。要求：

1. 对于每一个点，在其距离R的范围内必须至少有一个被标记的点（如果点本身被标记，则认为满足条件）
2. 在满足上述条件的情况下，尽可能减少被标记的点的数量

算法思路

这个问题可以使用贪心算法高效解决，基本思路如下：

1. 排序：首先将所有点按照位置从小到大排序
2. 覆盖：从最左边的点开始，找到最远的能被当前标记点覆盖的点
3. 标记：在覆盖范围的边界处放置标记点
4. 重复：移动到下一个未被覆盖的点，重复上述过程

代码实现

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

#define MAX_N 1000

int N, R;
int X[MAX_N] = {1, 7, 15, 20, 30, 50};

void solve() {
    // 首先对点进行排序
    sort(X, X + N);
    
    int i = 0;          // 当前处理的点的索引
    int marked_count = 0; // 被标记的点的数量
    
    while (i < N) {
        // 当前未覆盖区域的最左点
        int leftmost_uncovered = X[i];
        
        // 向右移动，找到第一个不能被leftmost_uncovered + R覆盖的点
        while (i < N && X[i] <= leftmost_uncovered + R) {
            i++;
        }
        
        // 标记点是在上一个点（即X[i-1]）
        int marked_point = X[i - 1];
        marked_count++;
        
        // 跳过所有能被当前标记点覆盖的点
        while (i < N && X[i] <= marked_point + R) {
            i++;
        }
    }
    
    cout << "最少需要标记的点数量: " << marked_count << endl;
}

int main() {
    N = 6;  // 点的数量
    R = 10; // 覆盖半径
    
    solve();
    
    return 0;
}

算法解析

让我们用示例数据 X = {1, 7, 15, 20, 30, 50} 和 R = 10 来逐步分析算法：

1. 初始状态：排序后数组不变，i=0
2. 第一轮：
   • leftmost_uncovered = 1
   • 找到第一个超过1+10=11的点：15（i=2）
   • 标记点选择X[1]=7
   • 跳过所有能被7+10=17覆盖的点：跳过15（i=3），20超过17停止
   • 标记计数=1
3. 第二轮：
   • leftmost_uncovered = 20
   • 找到第一个超过20+10=30的点：30（i=4）实际上30=30，所以继续到50（i=5）
   • 标记点选择X[4]=30
   • 跳过所有能被30+10=40覆盖的点：50超过40停止
   • 标记计数=2
4. 第三轮：
   • leftmost_uncovered = 50
   • 没有更多点，标记点选择X[5]=50
   • 标记计数=3

最终结果为3个标记点（7,30,50）

复杂度分析

• 时间复杂度：O(N log N)，主要由排序步骤决定
• 空间复杂度：O(1)，只使用了常数个额外空间

实际应用

这种贪心算法可以应用于许多实际问题，如：

• 无线基站部署问题
• 监控摄像头布置
• 路灯安装规划

通过这种策略，我们可以在满足覆盖要求的前提下，最小化资源的使用量。