1.算法
本题是一道贪心题,和《算法艺术与信息学竞赛》中的“照亮的山景”题极为相似。
(1)首先我们求出在每个岛屿放雷达以后在x轴上所能覆盖的区间,是在x轴的上的一个线段,即在这一段上放置雷达可以覆盖到该岛。
(2)我们把每个岛对应的线段找出来,只要在这些线段上放置一些雷达,使得所有的线段上都有雷达即可符合题意(注意如果半径为0或者坐标的y轴小于半径的话将无法完成覆盖,输出-1)。
(3)我们将线段根据左端点排序,找出如果一个线段包含另一个线段,则可以忽略外面的那一个线段(道理很简单),将其设为无效。
(4)在剩下的线段中从左往右遍历,对于每个线段,尽量选取该线段的最右边的点作为雷达,如果之前有雷达在该线段上,则跳过该线段。
(5)每次加一个雷达将计数器加一,最后可以得到解。
2.实现
(1)特别注意对于-1情况的判断,注意如果半径为0或者坐标的y轴小于半径的话将无法完成覆盖。
(2)边读边判断的时候要确保改组所有的数据都读完才能输出-1继续下一组的处理。
(3)在判断x轴上线段是否因为包含其他线段而无效时,可以从右往左遍历从而一次遍历完成判断。
(4)在放置雷达时需要从左往右遍历,这里需要设置一个很小的doule值,以方便第一个雷达的选取,这个值要比integer的最小值的两倍还要小一点,故设为-5000000000。
3.代码
Problem: 1328 User: godfrey90
Memory: 368K Time: 79MS
Language: G++ Result: Accepted
#include <cstdio>
#include <cmath>
struct unit {
double h;
double t;
bool able;
};
void work(int id,int m, int n);
bool get_ht(int r,int x,int y,double *ph,double *pt);
int main() {
int m, n;
int id=0;
scanf("%d %d", &m, &n);
while (!((m == 0) && (n == 0))) {
work(id++,m, n);
scanf("%d %d", &m, &n);
}
return 1;
}
void work(int id,int m, int n) {
//init
int x,y;
unit arr[1000];
int p = 0;
bool flag = true;
for (int i = 0; i < m; i++) {
scanf("%d %d", &x, &y);
if(!get_ht(n,x,y,&(arr[i].h),&(arr[i].t)))
flag = false;
arr[p++].able = true;
}
if(!flag){
printf("Case %d: -1\n",id+1);
return;
}
//sort
int len = p;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (arr[i].h > arr[j].h) {
unit temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
//disable the useless one
int tail = arr[len - 1].t;
for (int i = len - 2; i >= 0; i--) {
if (arr[i].t >= tail) {
arr[i].able = false;
} else {
tail = arr[i].t;
}
}
//find the radar
int count = 0;
double last = -5000000000;
for (int i = 0; i < len; i++) {
if ((arr[i].able) && (arr[i].h > last)) {
count++;
last = arr[i].t;
}
}
printf("Case %d: %d\n",id+1,count);
}
bool get_ht(int r,int x,int y,double *ph,double *pt){
if((r<0)||(r*r-y*y<0)) return false;
double dlt = sqrt(r*r-y*y);
*ph = x-dlt;
*pt = x+dlt;
return true;
}
分享到:
相关推荐
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
poj 3720解题报告poj 3720解题报告poj 3720解题报告poj 3720解题报告
poj1691解题报告 题目来源:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1691(POJ No.1691) 解法: 搜索
poj2828解题报告,希望能帮到志同道合的算法爱好者
北大poj解题报告,希望能帮到软件工程的同学,每天一道,持之以恒,熟能生巧,与您共勉!
北大POJ1328-Radar Installation 解题报告+AC代码
北大ACM1316解题报告
Problem 1061 青蛙的约会 poj解题报告。有源码。可直接提交C++实现
这是我发的第二篇解题报告,写的不怎么的。呵呵!!!!!
ACM POJ 解题报告北大POJ 大量解题代码
ACM Poj Pku 解题报告答案 打包 下载 600多题 史上最全 不是网上乱传的200多题,更不是100多题就挂着10分才能下的题 下了这个 大家也不要浪费分数去下载其它版本的了,基本上都有 共享 一起进步 中国加油 ACMer...
本人整理的POJ解题报告,一共有250道题
不错的资源 收集了网上的一些解题报告 方便同学们学习参考
北大ACM在线评测系统POJ的题目解题报告。涵盖各种类型的acm题目。值得参考借鉴。打包下载。