2018-1-31

其實(shí)就是貪心，每次將所選的點(diǎn)盡可能的向右，那么我們所需的就會(huì)盡可能的少了。。。

#include<iostream> #include<algorithm> #include<cmath> #define MIN 1e-5 using namespace std;const int N = 1000;struct zb{double xz,xy; }s[N+1];int n,r;//計(jì)算出可以覆蓋該島嶼的發(fā)射器的坐標(biāo)左右邊界 void cal(int i,double p,double q){double d=sqrt(r*r-q*q);s[i].xz=p-d;s[i].xy=p+d; }//按照右邊界進(jìn)行排序 bool cmp(struct zb a,struct zb b){ return a.xy<b.xy; }int main(){int cnt=1;double p,q;while(cin>>n>>r){if (n==0&&r==0) break;bool flag=false;for (int i=1;i<=n;i++){cin>>p>>q;if (q>r||q<0){flag=true;continue;}cal(i,p,q);}//所給數(shù)據(jù)不可能有解的情況，不能直接輸出然后continue，而是要等待它輸出完if (flag){cout<<"Case "<<cnt<<": -1"<<endl;cnt++;continue;}if (n==0||n==1){cout<<"Case "<<cnt<<": "<<n<<endl;cnt++;continue;}sort(s+1,s+n+1,cmp);//排序int res=0,i=1;double ee=s[1].xy;while (i<=n){while (s[i].xz<=ee&&i<=n){i++;}if (i<=n) ee=s[i].xy;res++;}cout<<"Case "<<cnt<<": "<<res<<endl;cnt++;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的poj1328 区间贪心 挑战程序设计竞赛的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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