噴水裝置（一）

時間限制：3000?ms ?|? 內存限制：65535?KB 難度：3 描述現(xiàn)有一塊草坪，長為20米，寬為2米，要在橫中心線上放置半徑為Ri的噴水裝置，每個噴水裝置的效果都會讓以它為中心的半徑為實數(shù)Ri(0<Ri<15)的圓被濕潤，這有充足的噴水裝置i（1<i<600)個，并且一定能把草坪全部濕潤，你要做的是：選擇盡量少的噴水裝置，把整個草坪的全部濕潤。 輸入

第一行m表示有m組測試數(shù)據(jù)
每一組測試數(shù)據(jù)的第一行有一個整數(shù)數(shù)n，n表示共有n個噴水裝置，隨后的一行，有n個實數(shù)ri，ri表示該噴水裝置能覆蓋的圓的半徑。

輸出

輸出所用裝置的個數(shù)

樣例輸入

2 5 2 3.2 4 4.5 6 10 1 2 3 1 2 1.2 3 1.1 1 2

樣例輸出

2 5





開始的時候把提議理解錯了，還以為給出半徑的圓都是無限呢！無語
這個題想法就是 ：貪心算法，每次都要選擇半徑最大的，自然用的就最少了！



1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6 7 double r[601]; 8 bool cmp(double a,double b) 9 { 10 return a>b; 11 } 12 13 int main() 14 { 15 int N,n,i; 16 double sum; 17 scanf("%d",&N); 18 while(N--) 19 { 20 scanf("%d",&n); 21 for(i=0;i<n;i++) 22 scanf("%lf",&r[i]); 23 sort(r,r+n,cmp); 24 double l=20; 25 int cot=0; 26 while(l>0) 27 { 28 l-=2*sqrt(r[cot]*r[cot]-1); 29 cot++; 30 } 31 printf("%d\n",cot); 32 } 33 }

?

轉載于:https://www.cnblogs.com/Eric-keke/p/4695461.html

總結

以上是生活随笔為你收集整理的喷水装置（一）--nyoj题目6的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。