原题: http://acm.nyist.net/JudgeOnline/problem.php?pid=6
//思路:根据喷水装置的半径,我们可以将它们转化为一个有效的喷水范围(线段),每次选择范围最长的,直到覆盖完整个长度 //关键在于转化 喷水装置的有效覆盖范围，贪心体现在每次取长度最长的线段 #include<iostream> #include<cstdio> #include<algorithm> #include<math.h> using namespace std; double r[601]; int cmp(const void *aa,const void * bb) { double a=*(double*)aa; double b=*(double*)bb; return a<b; } int main() { const double w=2; const double l=20; int t; scanf("%d",&t); while(t--) { int n; int pos=0; scanf("%d",&n); for(int i=0;i<n;i++) { double a; scanf("%lf",&a); if(a>w/2) { r[pos]=2*sqrt(a*a-w*w/4); pos++; } } // sort(r,r+pos,cmp); qsort(r,pos,sizeof(r[0]),cmp); double ei=0; int cnt=0; for(int i=0;i<pos;i++) { ei=ei+r[i]; cnt++; if(ei>=l){ break; } } printf("%d\n",cnt); } return 0; }