NYOJ-12 喷水装置2（贪心 区间覆盖）

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #define MAX 10000+1 using namespace std; struct node{ double left,right; }; bool cmp_left(struct node a, struct node b){ return a.left<b.left; } int main(){ int T; int n,w,h; int count,flag; double circle_x,circle_r,half,now_len,Max; struct node a[MAX]; cin>>T; while(T--){ count=0;//所需装置的个数 flag=1; now_len=0;//已覆盖的长度 cin>>n>>w>>h; half=h/2.000000; for(int i=0;i<n;i++){ double temp; cin>>circle_x>>circle_r; temp=sqrt(circle_r*circle_r-half*half); if(temp>0){ a[i].left=circle_x-temp;//左端点 a[i].right=circle_x+temp;//右端点 } } sort(a,a+n,cmp_left);//左端点从小到大排序 while(now_len<w){ Max=0; for(int i=0;i<n&&a[i].left<=now_len;i++){ if((a[i].right-now_len)>Max) Max=a[i].right-now_len;//用来选出左端点满足条件的线段中，右端点最大的线段 } if(Max==0){ flag=0;//没有左端点符合的 break; } else{ count++; now_len+=Max;//更新覆盖到的区间 } } if(flag==1) cout<<count<<endl; else cout<<"0"<<endl; } return 0; }