南阳OJ-6-喷水装置（一）

题目链接：

http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=6

题目大意：

现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0<Ri<15)的圆被湿润，这有充足的喷水装置i（1<i<600)个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。

思路：

一开始以为是区间问题，后面发现每个喷水装置没有固定的点，只考虑覆盖长度即可，所以瞬间简化成n个数取出前x个使得其大于20即可。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int maxn = 1e6 + ;

 int T, n;

 double a[];

 int main()

 {

     cin >> T;

     while(T--)

     {

         cin >> n;

         double x;

         int tot = ;

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

         {

             cin >> x;

             if(x <= )continue;

             a[tot++] = 2.0 * sqrt(x * x - );

         }

         sort(a, a + tot);

         int ans = ;

         double sum = 0.0;

         for(int i = tot - ; i >= ; i--)

         {

             sum += a[i];

             ans++;

             if(sum >= )break;

         }

         cout<<ans<<endl;

     }

     return ;

 }

传送门：喷水装置（二）