刷题与ZZ错误记录14

POJ-1328 Radar Installation

题面

【VJudge】 【POJ】

多组测试数据
给你n个坐标上的点, n <= 1000
你可以在x轴上放置雷达,每个雷达的辐射半径都是d
现在问你辐射到所有的点至少需要几个雷达,如果辐射不到所有的点输出-1

总结

一开始我有一个愚蠢的想法:尽可能将每一个新的点都放在圆的边缘上。

不过正解是这样的:
对于一个点A,其被圆包括的圆心的范围如红线所示:
1pmSxg.png
这样我们可以将这个问题转换为区间问题:将“一个点被圆包括”修改为“圆心的区间”,这样问题就变成了:选择最少的点来覆盖所有的区间。

这样这题就变成了一道显而易见的贪心题:将所有的区间按照左端点排序,然后选择第一个区间,点的数量设为1。接着处理每一个区间:若下一个区间与目前区间有交集,那么目前区间与该区间求交集(将区间的右端点左移,因为若取该区间右端点右边,就没有一个点覆盖该区间),否则将目前区间替换为该区间,然后点的数量+1。

槽点

  1. (CE) :POJ不可以用万能头!
  2. (WA) :因为陆地实际上是在x轴的上方,所以删去了fabs操作;当我意识到区间的右端点需要左移时我重写了一遍。
  3. (WA) :因为这题支持多组数据,但我不小心把结束该组数据运算的语句写成了break!(实际上是continue

AC代码

//#include<bits/stdc++.h>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
pair<double,double> st[3000];
int n,d,ans,a,b,T,x,y;
bool flag;double range;
int main(){
    T=0;
    while(1){
        scanf("%d%d",&n,&d);
        if(n==0 && d==0){
            return 0;
        }
        T++;
        flag=true;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&x,&y);
            if(fabs(y)>d)flag=false;
            if(flag){
                st[i]=make_pair(x-sqrt(pow(d,2)-pow(y,2)),x+sqrt(pow(d,2)-pow(y,2)));
            }
        }
        if(!flag){
            printf("Case %d: -1\n",T);
            continue;
        }
        sort(st+1,st+1+n);
        /*for(int i=1;i<=n;i++){
            printf("(%f,%f)\n",st[i].first,st[i].second);
        }*/
        ans=1;a=1;b=2;range=st[1].second;
        for(b=2;b<=n;b++){
            if(range>=st[b].first){
                range = min(range,st[b].second);
            }else{
                range = st[b].second;
                ans++;
            }
        }
        printf("Case %d: %d\n",T,ans);
    }
}

页面: 1 2 3 4 5 6 7

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注