简答题 偏难
#22125

T2、超速检测(detect)

T2、超速检测(detect)


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; bool Mbegin; void File_Work(){ freopen("detect.in","r",stdin); freopen("detect.out","w",stdout); } const int N=1e5+8; int n,m,L,V,p[N],d[N],v[N],a[N]; struct Interval{ int l,r; void init(){ l=r=0; } friend bool operator &lt;(Interval a,Interval b){ if(a.r!=b.r) return a.r&lt;b.r; return a.l&lt;b.l; } }itv[N]; bool check(int pos,int i){ int x=p[pos]-d[i]; int v2=v[i]*v[i]+2*a[i]*x; if(V*V&lt;v2) return 1; return 0; } void MAIN(){ for(int i=1;i&lt;=n;i++) p[i]=0,itv[i].init(); cin&gt;&gt;n&gt;&gt;m&gt;&gt;L&gt;&gt;V; for(int i=1;i&lt;=n;i++) cin&gt;&gt;d[i]&gt;&gt;v[i]&gt;&gt;a[i]; for(int i=1;i&lt;=m;i++) cin&gt;&gt;p[i]; sort(p+1,p+m+1); int ans1=0; for(int i=1;i&lt;=n;i++){ if(p[m]&lt;d[i]) continue; int pos=lower_bound(p+1,p+m+1,d[i])-p; if(a[i]==0&amp;&amp;v[i]&gt;V) itv[++ans1]={pos,m}; else if(a[i]&lt;0){ int x=p[pos]-d[i]; int v2=v[i]*v[i]+2*a[i]*x; if(V*V&lt;v2){ int l=pos,r=m,res=0; while(l&lt;=r){ int mid=(l+r)/2; if(check(mid,i)==1){ res=mid; l=mid+1; } else r=mid-1; } itv[++ans1]={pos,res}; } } else if(a[i]&gt;0){ int x=p[m]-d[i]; int v2=v[i]*v[i]+2*a[i]*x; if(V*V&lt;v2){ int l=pos,r=m,res=0; while(l&lt;=r){ int mid=(l+r)/2; if(check(mid,i)==1){ res=mid; r=mid-1; } else l=mid+1; } itv[++ans1]={res,m}; } } } cout&lt;&lt;ans1&lt;&lt;' '; sort(itv+1,itv+ans1+1); int ans2=0,cur; for(int i=1;i&lt;=ans1;i++){ if(itv[i].l&lt;=cur&amp;&amp;cur&lt;=itv[i].r) continue; ans2++; cur=itv[i].r; } cout&lt;&lt;m-ans2&lt;&lt;'\n'; } bool Mend; int main(){ // File_Work(); ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cerr&lt;&lt;fixed&lt;&lt;setprecision(3)&lt;&lt;(&amp;Mbegin-&amp;Mend)/1048576.0&lt;&lt;" MB\n\n\n"; int testid=0,testnum=1; // cin&gt;&gt;testid; cin&gt;&gt;testnum; while(testnum--) MAIN(); cerr&lt;&lt;"\n\n\n"&lt;&lt;fixed&lt;&lt;setprecision(0)&lt;&lt;1e3*clock()/CLOCKS_PER_SEC&lt;&lt;" ms"; return 0; }</pre>
这道题暂未补解析。