算法1
(根据右端点排序后求解) $O(n\log n)$
刚开始的固定思路是:求解雷达的坐标,然后画出圆,判断其他的小岛在不在这个圆里面,然后这里用到的贪心:先根据所有小岛x
坐标排序,然后按照区间合并的方法判断接下来的小岛能否被这个圆包含求解,但是答案始终有问题。估计是哪里考虑不全面,主要是太难了。
然后就是y总根据右端点排序后求解的思路了!
主要就是进行1个思维转化,求出每个小岛支持的雷达的x
坐标的范围,然后贪心体现在:我们考虑所有有交集的区间,他们就可以只取1个点,那么得到的答案就是最优解。
那么接下来就是区间选点。2种方法,1:根据右端点排序,2:根据左端点排序。
1:右端点排序后,(假定1号的右端点已经被选)只需要根据2、3…号区间左端点判断跟1号区间是否相交。
根据贪心,我们将最初的点选在1号区间的右端点$l_1$,就能更大范围地覆盖,那么判断2、3…区间能否选在这个点的要求就是他们的左端点<=
$l_1$,假如说<=
,那么continue。假如说>
,那么重新开始新一轮的选点。代码如下。
参考文献:y总
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Comparator;
public class Main {
static class node{
double l, r;
node(double l, double r){
this.l = l;
this.r = r;
}
}
static int N = 1010;
static int n, d;
static node a[] = new node[N];
static int dx[] = new int[N];
static int dy[] = new int[N];
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken(); n = (int) st.nval;
st.nextToken(); d = (int) st.nval;//雷达半径
for (int i = 0; i < n; i++) {//用1-n方便一些
st.nextToken(); dx[i] = (int) st.nval;
st.nextToken(); dy[i] = (int) st.nval;
}
for (int i = 0; i < n; i++) {
if(dy[i]>d) {
System.out.println("-1");
return ;
}
a[i] = new node(dx[i]-Math.sqrt(d*d-dy[i]*dy[i]),dx[i]+Math.sqrt(d*d-dy[i]*dy[i]));
}
Arrays.sort(a, 0, n, new Comparator<node>() {//将区间按照右端点升序排序
@Override
public int compare(node o1, node o2) {
// TODO Auto-generated method stub
if(o1.r - o2.r >= 0) return 1;
return -1;
}
});
int ans = 1;
double start = a[0].l;//这里的start其实没啥用
double end = a[0].r;
for (int i = 1; i < n; i++) {
if(a[i].l <= end) ;//说明这2个区间有交集 那么什么都不做 把雷达放在交集处 贪心贪到最开始的右端点 即end
else {
end = a[i].r;//没有交集 那么重新定义end
ans++;
}
}
System.out.println(ans);
}
}
算法2
(根据左端点排序后求解) $O(n\log n)$
2:这个方法其实跟1很像,确定左端点,直接计算区间相交后的区间,从而确定下1个区间是否包含这个相交的区间,如果包含,那么continue,不然就开始新一轮的选点。
参考文献:y总
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Comparator;
public class Main {
static class node{
double l, r;
node(double l, double r){
this.l = l;
this.r = r;
}
}
static int N = 1010;
static int n, d;
static node a[] = new node[N];
static int dx[] = new int[N];
static int dy[] = new int[N];
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken(); n = (int) st.nval;
st.nextToken(); d = (int) st.nval;//雷达半径
for (int i = 0; i < n; i++) {//用1-n方便一些
st.nextToken(); dx[i] = (int) st.nval;
st.nextToken(); dy[i] = (int) st.nval;
}
for (int i = 0; i < n; i++) {
if(dy[i]>d) {
System.out.println("-1");
return ;
}
a[i] = new node(dx[i]-Math.sqrt(d*d-dy[i]*dy[i]),dx[i]+Math.sqrt(d*d-dy[i]*dy[i]));
}
Arrays.sort(a, 0, n, new Comparator<node>() {//将区间按照左端点升序排序
@Override
public int compare(node o1, node o2) {
// TODO Auto-generated method stub
if(o1.l - o2.l >= 0) return 1;
return -1;
}
});
int ans = 1;
double start = a[0].l;
double end = a[0].r;
for (int i = 1; i < n; i++) {
if(a[i].l <= end) {
start = Math.max(start, a[i].l);
end = Math.min(end, a[i].r);
}
else {
start = a[i].l;
end = a[i].r;
ans++;
}
}
System.out.println(ans);
}
}