P1033 自由落体【洛谷算法习题】

P1033 自由落体网页链接P1033 自由落体题目描述在高为H HH的天花板上有n nn个小球体积不计位置分别为0 , 1 , 2 , ⋯ , n − 1 0,1,2,\cdots,n-10,1,2,⋯,n−1。在地面上有一个小车长为L LL高为K KK距原点距离为S 1 S_1S1​。已知小球下落距离计算公式为d 0.5 × g × ( t 2 ) d0.5 \times g \times (t^2)d0.5×g×(t2)其中g 10 g10g10t tt为下落时间。地面上的小车以速度V VV前进。如下图小车与所有小球同时开始运动当小球距小车的距离≤ 0.0001 \le 0.0001≤0.0001(感谢 Silver_N 修正) 时即认为小球被小车接受小球落到地面后不能被接受。请你计算出小车能接受到多少个小球。输入格式H , S 1 , V , L , K , n H,S_1,V,L,K,nH,S1​,V,L,K,n1 ≤ H , S 1 , V , L , K , n ≤ 100000 1 \le H,S_1,V,L,K,n \le 1000001≤H,S1​,V,L,K,n≤100000输出格式小车能接受到的小球个数。输入输出样例 #1输入 #15.0 9.0 5.0 2.5 1.8 5输出 #11说明/提示当球落入车的尾部时算作落入车内。【题目来源】NOIP 2002 提高组第三题解题思路本题核心是通过物理公式推导区间范围判断统计小车可接收的小球数首先根据自由落体公式d 0.5 × g × t 2 d0.5×g×t²d0.5×g×t2g 10 g10g10推导小球落到小车顶部高度K KK的时间t m i n ( H − K ) / 5 t_{min}\sqrt{(H-K)/5}tmin​(H−K)/5​落到地面的时间t m a x H / 5 t_{max}\sqrt{H/5}tmax​H/5​小车以速度V VV向左移动t tt时间内位移为V × t V×tV×t因此小球i ii的水平位置需满足s 1 − t m a x × V ≤ i ≤ s 1 − t m i n × V L s1 - t_{max}×V ≤ i ≤ s1 - t_{min}×V Ls1−tmax​×V≤i≤s1−tmin​×VL小车有效水平范围最后统计该区间内且0 ≤ i n 0≤in0≤in的小球数量即为答案。该方法通过数学公式直接计算区间边界无需遍历所有小球时间复杂度O ( 1 ) O(1)O(1)适配n ≤ 1 e 5 n≤1e5n≤1e5的规模精准统计可接收的小球数。总结核心逻辑推导小球下落的时间区间结合小车位移计算可接收小球的水平区间统计区间内的小球数。关键操作计算t m i n t_{min}tmin​落到小车顶部、t m a x t_{max}tmax​落到地面推导小球水平位置的合法区间取与[ 0 , n ) [0,n)[0,n)的交集统计数量。效率保障纯数学公式计算无遍历操作时间复杂度O ( 1 ) O(1)O(1)适配题目数据规模n ≤ 1 e 5 n≤1e5n≤1e5。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e510;constll mod1e97;constll INF1e18;intmain(){ll n;doubleh,s1,v,l,k;cinhs1vlkn;doublet_maxsqrt(h/5);doublet_minsqrt((h-k)/5);ll bll(s1-t_min*vl),ell(s1-t_max*v);bmin(b,n);emax(e,0ll);coutb-eendl;return0;}