昨天把贪心看了一下。开始进入贪心的学习。

/* * ===================================================================================== * *       Filename:  poj 1328     * *    Description:  贪心+qsort *           先用计算出要覆盖每个点所需要在x轴上的区间(关键是要理解这点，不懂的可以看看程序)。用Node结构体存储。 *           注意要用double.因为sqrt要求的是double.然后每次从右边开始判断(即找 *           最大可能，贪心)。要注意不能覆盖情况的处理。具体的看程序的注释吧。 * * *        Version:  1.0 *        Created:  2012/5/8 13:31:17 *       Revision:  none *       Compiler:  gcc * *         Author:  Jason Damon  *   Organization:  XD University * * ===================================================================================== */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define MAXN 1005struct Node{    double right,left;}node[MAXN];int cmp(const void *a,const void *b){    return ((Node*)a)->left>=((Node*)b)->left?1:-1;}int main(){    int i,n,d,x,y,id=0,cnt;    double point,l;    bool flag;    freopen("in.txt","r",stdin);    id=1;    while(scanf("%d%d",&n,&d),n+d)    {        if(d<=0)        {                    }        flag=false;        for(i=0; i
          
           d) { flag=true; } l=sqrt(double(d*d-y*y)); //用于求能覆盖这点的圆的圆心区间 // 覆盖区间 node[i].left=x-l; node[i].right=x+l; } if(flag) { printf("Case %d: -1\n",id); id++; continue; } qsort(node,n,sizeof(Node),cmp); point=node[0].right;//取第一点的右端点 cnt=1; for(i=1; i
           
            point) { cnt++; point=node[i].right; } else { if(node[i].right