问题描述
Q1:设有一条边远山区的道路AB，沿着道路AB分布着n所房子。这些房子到A的距离分别是d1,d2,…,dn(d1<d2<…<dn)。为了给所有房子的用户提供移动电话服务，需要在这条道路上设置一些基站。为了保证通讯质量，每所房子应该位于距离某个基站的4Km范围内。设计一个算法找基站的位置，并且使得基站的总数最少。
算法
贪心策略是，从第一个房子开始取d1+4的距离，检测下一个房子有没有被覆盖，若没有，则在下一个房子如d2开始再取d2+4。若已经覆盖，则跳过，检测下一个，直到检测完为止。
代码
//Q1:设有一条边远山区的道路AB，沿着道路AB分布着n所房子。这些房子到A的距离分别是d1,d2,…,dn(d1<d2<…<dn)。
//为了给所有房子的用户提供移动电话服务，需要在这条道路上设置一些基站。为了保证通讯质量，每所房子应该位于距离某个
// 基站的4Km范围内。设计一个算法找基站的位置，并且使得基站的总数最少。
// 算法：贪心策略是，从第一个房子开始取d1+4的距离，检测下一个房子有没有被覆盖，若没有，则在下一个房子如d2开始
// 再取d2+4。若已经覆盖，则跳过，检测下一个，直到检测完为止。
//算法复杂度：
// 关键词：贪心
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue> // 使用队列
#include<cstring>
using namespace std;
class Ques20201020
{
public:
void test(vector<int>& distances) {
vector<int> result;
result.push_back(distances[0]+4); // 从第一个房子开始取d1+4的距离
for (int i = 1; i < distances.size(); i++) {
if (result[result.size()-1]+4> distances[i]) {
continue;
}
else {
result.push_back(distances[i]+4);
}
}
// 打印结果
for (int i = 0; i < result.size(); i++) {
cout << " " << result[i];
cout << endl;
}
}
private:
};
//Ques20201020
int main() {
Ques20201020 ques = Ques20201020();
vector<int> s = { 2,7,8,12,15 };
ques.test(s);
return 0;
}
证明
运行效果
