雷达题
最优雷达问题(贪心算法)
1.算法思路分析：
对于这个问题的样例输入输出，以及解题思路的分析步骤如下：
首先建立基本数学模型，由于题目提示要采用贪心算法的策略，所以在考虑最优解的情况下，我们的所有雷达的设置点位都应该建立在x轴线上面，通过队长的思路的提示，对右端点进行升序排列，能成功覆盖的岛屿部分直接忽略，采用贪心的思路，进行取舍，取最优解的情况，于是x轴线上求取关键点成为这道题我们组的关键解题思路。
然后，这个问题主要被我们分为三个主要的算法分支部分，第一步，出现y坐标大于d长度的点就直接进行取舍，并通过flag的值来进行输入结束后printf("-1")的关键判断。第二步，在一般情况下，不满足第一步的条件，这是对问题进行再一次的分解，首先利用下面的公式求出在x轴和y轴的坐标.
| Bash |
|---|
| a[i].l=x[i]-sqrt(d*d-y[i]*y[i]); //求出左端点
a[i].r=x[i]+sqrt(d*d-y[i]*y[i]); //求出右端点
|
之后对右端点进行排序，排序后，进入判断部分，分为一下三种情况
- 1.在i==1的时候，把右端点的部分的值用temp变量存起来，然后把第一个雷达的位置定位到最右侧，ans++。
- 2.在判断下一个节点的左端点部分是否小于上一个节点的右端点部分，如果满足条件，则直接检查下一个节点。
- 3.否则不满足上述情况的时候，这是一个节点显然不够包括所有岛屿，于是重新在此节点上对后面的temp进行更新。
- 执行完之后再次进入循环判断问题
注意：上述情况都是建立在在满足排序条件之后的。
2.数据结构的选择和设计：
由第一部分的分析，我们首先使用MAXN分配一个较大的数，给一个足够的空间，防止溢出。然后采用一维数组进行存储数据内容。
然后问题的关键部分就是对于左右端点的存储问题，我们经过小组的讨论使用一个结构体进行存储，便利后面的排序和遍历
| C++ |
|---|
| 1. x[MAXN] y[MAXN] //用来存储某一结点的x，y坐标
2. struct node{
double l,r; //定义结构体存储左右端点
}a[MAXN];
|
3.算法设计代码
| C++ |
|---|
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58 | #include <iostream>
#include <algorithm>
#include <cstdio>
#include <math.h>
#define MAXN 10001
using namespace std;
int n,ans=0;//ans用来存储结果
double d,temp,x[MAXN],y[MAXN];
struct node{
double l,r; //定义结构体存储做右端点
}a[MAXN];
double cmp(node aa,node bb){
return aa.r<bb.r; //按右端点进行升序排列
}
int main()
{
int flag = 1;
do{
cin>>n>>d;
for(int i=1;i<=n;i++){
{
cin>>x[i]>>y[i];
if(y[i]>d){
flag=0; //使用flag来进行标志是否无法覆盖岛屿
}
a[i].l=x[i]-sqrt(d*d-y[i]*y[i]); //求出左端点
a[i].r=x[i]+sqrt(d*d-y[i]*y[i]); //求出右端点
}
}
sort(a+1,a+n+1,cmp); //对a1到an进行排序
//由于已经经过升序排列，这时只需要最小右端点部分进行循环检测，进行添加节点即可
for(int i = 1;i<=n;i++){
if(!flag){
printf("-1\n"); //无法覆盖输出-1
return 0;
}
else if(i==1){
temp=a[i].r; //把第一个雷达定位到最右侧
ans++;
}
else if(temp>a[i].l) //如果覆盖，则返回循环开始部分
continue;
else{
temp=a[i].r; // 否则防止一个新的雷达
ans++;
}
}
if(n!=0&&d!=0){
cout<<ans<<endl; //当n和d都不等于零的时候输出，避免最后一次0，0输出ans
}
ans=0; //执行完成一个测试集后把ans清零
}while(!(n==0 && d==0));
return 0;
}
|
文章总观看量次