題干：

題目大意：

有一塊草坪，長為l，寬為w，在它的水平中心線上有n個位置可以安裝噴水裝置，各個位置上的噴水裝置的覆蓋范圍為以它們自己的半徑ri為圓。求出最少需要的噴水裝置個數，如果無論如何都不能覆蓋，就輸出-1。

解題報告：

? ?這題就是個區間覆蓋問題的變形，，雖然給的是一個個的圓，但是我們不難發現求出與上下邊的交點，這一部分區域才是我們的有效區域，然后求個區間覆蓋就行了、、、nlogn的算法按說不應該TLE啊，，，但是該優化的都優化了還是TLE，看了題解發現有個剪枝，，（但是說實話這個題卡時間沒必要吧、、TLE變0ms）

? ?emmm今天又想了一下好像不是TLE的問題，，這樣會WA吧、、因為本來可能覆蓋不到的地方你都變成覆蓋得到了、、你求邊界那里就不對、、對一個負數去開平方根？？？可能這樣會認為是TLE吧、、

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; struct Node {double st,ed;Node(){}Node(double st,double ed):st(st),ed(ed){}bool operator<(const Node & b) const{if(st != b.st) return st < b.st;return ed > b.ed;} } node[MAX]; int tot,cnt; int main() {int n;double l,w,x,r;while(~scanf("%d%lf%lf",&n,&l,&w)) {tot=cnt=0;for(int i = 1; i<=n; i++) {scanf("%lf %lf",&x,&r);if(r < w/2) continue;//cin>>x>>r;//cout << x<< r << endl;node[++tot] = Node(x-sqrt(r*r-w*w/4),x+sqrt(r*r-w*w/4));//cout << x-sqrt(r*r-w*w/4) << endl;}sort(node+1,node+tot+1);//for(int i = 1; i<=tot; i++) printf("%f %f\n",node[i].st,node[i].ed);double cure,curs;curs=cure=0;int flag = 0;for(int i = 1; i<=tot; ) {if(node[i].st > curs) {break; }while(i<=tot && node[i].st<=curs) {if(node[i].ed > cure) {cure = node[i].ed;}i++;}cnt++;curs = cure;if(curs >= l) {flag=1;break;}}if(flag == 0) puts("-1");else printf("%d\n",cnt);}return 0 ;}

還有一個沒有排序的算法、這樣寫就不需要加剪枝了。，。但是不知道為什么這樣可以。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的*【UVA - 10382】Watering Grass（贪心，区间覆盖问题，思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

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