题目描述

Description

一条很长的乡村公路（我们可以想象这条公路是一条长线段，有一个西端点和一个东端点），公路旁稀疏的分布着一些房子。
我们把公路的西端点固定在坐标0上，东端点为某远处。

假设这些房子的居民都使用蜂窝移动电话，现在需要把移动电话基站放在这条路旁的某些点上，使得每个房子都在其中一个
基站4公里之内。

注意：房子和基站都建立在公路旁而不远离公路，即可以认为房子和基站都是公路直线上的点。

给出一个有效算法，使得用尽可能少的基站来实现这个目标。

输入格式

第一行，房子的数量n （n<=100000）

第二行，房子分布的位置：h1 h2 … hn

输出格式

最少的基站数量，所有房子都能覆盖在某个基站之下（基站的有效距离为4公里）。

输入样例

6

1 12 8 3 4 15

输出样例

2

提示

此题比较简单。
（1）先将房子分布的位置进行排序。
（2）从左到右考虑基站安置的位置，要使得基站数最少，又要所有居民房子都被基站4km范围内覆
盖到，因此如果某个房子不在你当前安置的基站4km的距离内，那就最大距离4km的覆盖，这样基站
数最少。所以我们的策略是：将下一个基站安置在当前那个不在覆盖范围内房子向东4km远的距离。

代码

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
#include <iostream>
using namespace std;
void swap(int &a,int & b){
    int temp = a;
    a = b;
    b = temp;
}
int main() {
    int n;
    int i,j;
    int count = 1,base;
    cin >> n;
    int* house = new int[n];
    for (i = 0; i < n; i++){
        cin >> house[i];
    }
    for (i = 0; i < n-1; i++){
        for (j = i + 1; j < n; j++){
            if (house[i] > house[j]){
                swap(house[i],house[j]);
            }
        }
    }
    base = house[0] + 4;
    for(i = 1; i < n; i++){
        if (base < house[i] - 4){
            count++;
            base = house[i] + 4;
        }
    }
    cout << count << endl;
    return 0;
}