poj1328:Radar Installation——区间贪心

题目描述

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.

We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.

分析

以小岛为圆心,以d为半径作圆,圆与海岸线有相交、相切、相离三种情况

poj1328:Radar Installation——区间贪心

  • 相交

    则可求出范围[x-sqrt(d2 - y2),x+sqer(d2 - y2)],雷达可安装在此范围内任意位置

  • 相切

    雷达只能安装在[x,0]这点,即范围为[x, x]

  • 相离

    出现这类情况,则不可能有任何一个雷达可以覆盖该小岛,按照题目要求输出即可

题目求覆盖所有小岛最小的雷达数,即求区间重叠的情况下更少的雷达,优先选择区间左端点驾较小的

贪心策略

  • 每次只选择一个区间
  • 选择左端点最小的区间
  • 统计重叠区间数目

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;

const int MAXN = 1010;
struct Interval{        //区间结构体
    double left;        //左端点
    double right;       //右端点
};
Interval rangs[MAXN];   //区间数组

int cmp(Interval a, Interval b){
    return a.left < b.left;
}

int main(){
    int n, d, x, y;
    int caseNumber = 0;
    while(scanf("%d%d", &n, &d) != EOF){
        if(n == 0 && d == 0){
            break;
        }
        bool flag = true;
        for(int i = 0; i < n; ++i){
            scanf("%d%d", &x, &y);
            if(y > d){          //相离情况
                flag = false;
            }
            //对于每一个小岛,雷达可以放置的区间
            double t = sqrt(1.0 * d * d - y * y);
            rangs[i].left = x - t;
            rangs[i].right = x + t;
        }
        if(!flag){  //不能覆盖所有小岛,即出现相离情况
            printf("Case %d: %d\n", ++caseNumber, -1);
            continue;
        }
        //按区间左端点优先排序
        sort(rangs, rangs + n, cmp);

        //初始为第一个区间的右端点
        double current = rangs[0].right;
        int ans = 1;
        //遍历剩下的区间
        for(int i = 1; i < n; ++i){
            if(rangs[i].left <= current){   //区间有重叠
                //current更新为较小的区间右端点
                current = min(rangs[i].right, current);
            }
            else{       //区间无重叠
                current = rangs[i].right;   //直接更新current
                ans++;                      //雷达+1
            }
        }
        printf("Case %d: %d\n", ++caseNumber, ans);
    }
    return 0;
}
上一篇:网页前端第四次学习


下一篇:寒假打卡-算法-差分--例题AcWing 100. IncDec序列