题目：给出一个坐标系，将x轴看作海岸，在x轴的上方会出现一些质点（代表小岛），现在要在岸上建造一些灯塔，要求所有的小岛都要被至少一个灯塔照到，求最少要建造多少个灯塔。
分析：贪心的思路，每个小岛对应在海岸上对应一段区间，将这些区间按照左端排序，查找最少需要的个数，注意每次判断的右端会不断更新，按照每次判断的小岛的区间
收获：第一次做区间贪心的问题，没想到把小岛的对应的灯塔范围转化到坐标轴上。。。
贪心不一定是直观的，对于问题来说有时需要贪心一个整体的一部分，有时需要贪心一种类型转化出的另一种类型来求最佳结果，等非直观的情况。 第一次：对于贪心的思想有了进一步的认识。
#include<iostream> #include<stdio.h> #include<cmath> #include<algorithm> using namespace std; int m,n; struct rad { double x,y; double st,ed; } Rad[1005]; bool cmp (rad x1, rad x2) { return x1.ed<x2.ed; } bool get_st_and_ed(rad &x1) { x1.st=(x1.x-sqrt((1.0 *n*n)-(x1.y*x1.y))); x1.ed=(x1.x+sqrt((1.0 *n*n)-(x1.y*x1.y))); if(x1.y>n) { return false; } } int main () { int kase=1; while(~scanf("%d%d",&m,&n)&&m&&n) { bool flag=true; for(int i=0; i<m; i++) { scanf("%lf%lf",&Rad[i].x,&Rad[i].y); flag=get_st_and_ed( Rad[i]); } if(flag==true) { sort(Rad,Rad+m,cmp); // for(int i=0;i<m;i++) // { // printf("%lf %lf\n",Rad[i].st,Rad[i].ed); // } double max_ed=Rad[0].ed; int cnt = 1; for(int i=0; i<m; i++) { if(Rad[i].st>max_ed) { max_ed=Rad[i].ed; cnt++; } else if (Rad[i].ed<max_ed) { max_ed=Rad[i].ed; } } printf("Case %d: %d\n",kase ,cnt); } else { printf("Case %d: -1\n",kase ); } kase++; } return 0; }
