瞎搞-贪心-NOIP前42天-入门-喷水装置

本文主要是介绍瞎搞-贪心-NOIP前42天-入门-喷水装置，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作死三部曲：
Step 1

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)
#define random(l,r) ((l)+rand()%((r)-(l)+1))
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int inf=1e9+10,N=20000;
const double eps=1e-6;
struct node{double a,b;}p[N];
bool compare(node a,node b){ return a.a<b.a;}
int t,n;
double l,w,x,r;
int main(){ios::sync_with_stdio(false); cin.tie(0);cin>>t;while(t--){memset(p,0,sizeof(p));double last=0,now=0; int ans=0;cin>>n>>l>>w;rep(i,1,n){cin>>x>>r;if(r*2<=w) continue;p[i].a=x-sqrt((double)r*r-w*w/4.0f);p[i].b=x+sqrt((double)r*r-w*w/4.0f);}sort(p+1,p+1+n,compare);rep(i,1,n){if(p[i].a>last){if(now>0) ans++,last=now,now=0;else{ans=-1;break;}}if(p[i].b>=last) now=max(now,p[i].b);}if(last<l) cout<<0<<endl;else cout<<ans<<endl;}return 0;
}

到最后的时候now里可能还有值，也就是最后的那个喷水装置没被使用，因为最后一个不会在循环中被更新。因此导致答案错误。（本来可以覆盖的结果变成不能覆盖的了）。
Step 2:

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)
#define random(l,r) ((l)+rand()%((r)-(l)+1))
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int inf=1e9+10,N=20000;
const double eps=1e-6;
struct node{double a,b;}p[N];
bool compare(node a,node b){ return a.a<b.a;}
int t,n;
double l,w,x,r;
int main(){ios::sync_with_stdio(false); cin.tie(0);cin>>t;while(t--){memset(p,0,sizeof(p));double last=0,now=0; int ans=0;cin>>n>>l>>w;rep(i,1,n){cin>>x>>r;if(r*2<=w) continue;p[i].a=x-sqrt((double)r*r-w*w/4.0f);p[i].b=x+sqrt((double)r*r-w*w/4.0f);}sort(p+1,p+1+n,compare);rep(i,1,n){if(p[i].a>last){if(now>0) ans++,last=now,now=0;else{ans=-1;break;}}if(p[i].b>=last) now=max(now,p[i].b);}***if(now>0) ans++,last=now,now=0;***if(last<l) cout<<0<<endl;else cout<<ans<<endl;}return 0;
}

将最后本该使用的喷水装置使用了，以为要AC了，结果又WA了。。因为其实有时候最后这一个喷水装置不用的话也已经完全覆盖了，再多用答案就错了。
Step 3 AC代码：

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)
#define random(l,r) ((l)+rand()%((r)-(l)+1))
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int inf=1e9+10,N=20000;
const double eps=1e-6;
struct node{double a,b;}p[N];
bool compare(node a,node b){ return a.a<b.a;}
int t,n;
double l,w,x,r;
int main(){ios::sync_with_stdio(false); cin.tie(0);cin>>t;while(t--){memset(p,0,sizeof(p));double last=0,now=0; int ans=0;cin>>n>>l>>w;rep(i,1,n){cin>>x>>r;if(r*2<=w) continue;p[i].a=x-sqrt((double)r*r-w*w/4.0f);p[i].b=x+sqrt((double)r*r-w*w/4.0f);}sort(p+1,p+1+n,compare);rep(i,1,n){if(p[i].a>last){if(now>0) ans++,last=now,now=0;else{ans=-1;break;}}if(p[i].b>=last) now=max(now,p[i].b);}***if((now>0)&&(last<l)) ans++,last=now,now=0;***if(last<l) cout<<0<<endl;else cout<<ans<<endl;}return 0;
}