Southern SubregionalProblem B. Travelling Camera Problem

二分找区间 直接算

#include <bits/stdc++.h> using namespace std; const int maxn=300050; double x[maxn]; double a[maxn]; int main(){ int n,m; double rr; //cin>>m>>n>>rr; scanf("%d%d%lf",&m,&n,&rr); double r=sqrt(rr*rr-1.0); for(int i=0;i<m;i++){ scanf("%lf",&a[i]); //cout<<a[i].l<<" "<<a[i].r<<" "<<a[i].c<<endl; } double ans=0; int wh=0; for(int i=0;i<n;i++){ scanf("%lf",&x[i]); int midl=lower_bound(a,a+m,x[i]-r)-a; int midr=upper_bound(a,a+m,x[i]+r)-a-1; if(wh<midl){ ans+=a[midl]-a[wh]; wh=midl; //cout<<"sadsa"<<endl; } else if(wh>midr){ ans+=a[wh]-a[midr]; wh=midr; //cout<<"asda"<<endl; } //cout<<midl<<" "<<midr<<endl; } printf("%.1lf\n",ans); }