NYOJ 喷水装置（二）

题目转换成，每个水龙头在横坐标方向上覆盖的长度区间，转换后的问题就有点像会场安排问题了，然后接下来选的方案依据贪心，我们队这些个区间进行排序，依照区间的左端点按从小到大排序，然后从左往右选取，条件是当前区间的左端点在覆盖范围内，右端点最远。如果一次循环覆盖范围没有加大，就证明不能覆盖。

 #include<iostream>

 #include<cmath>

 #include<stdlib.h>

 #include<string.h>

 using namespace std;

 typedef struct

 {

     double start;

     double end;

 }SE;

 SE a[];

 int compare (const void *p1, const void *p2)

 {

     return (((SE *)p1)->start<((SE *)p2)->start)? :-;

 }

 int main()

 {

     int T;

     cin>>T;

     while(T--)

     {

         int N;

         double w, h;

         cin>>N>>w>>h;

         for(int i=; i<N; i++)

         {

             double x, r;

             cin>>x>>r;

             double tem = r*r-((double)h/)*((double)h/);

             if(tem>=)

                 tem = sqrt(tem);

             else

                 tem = ;

             a[i].start = x - tem;

             a[i].end = x+ tem;

         }

         qsort(a,N,(sizeof(a[])),compare);

         /*for(int i=0; i<K; i++)

         {

             cout<<a[i].start<<"    "<<a[i].end<<endl;

         }*/

         double st=, en=;

         int visit[];

         memset(visit,,sizeof(visit));

         int num = ;

         while(en<w)

         {

             double endest = en;

             for(int i=; i<N; i++)

             {

                 if(visit[i]==&&a[i].start<=en&&a[i].end>endest)

                 {

                     endest = a[i].end;

                 }

             }

             if(endest>en)

             {

                 en = endest;

                 num++;

             }

             else

             {

                 cout<<<<endl;

                 break;

             }

         }

         if(en>=w)

         {

             cout<<num<<endl;

         }

     }

     return ;

 }

巴特西

NYOJ 喷水装置（二）

最新文章

热门文章