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 ) d=0.5 \times g \times (t^2)d=0.5×g×(t2)，其中g = 10 g=10g=10，t 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,n（1 ≤ 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
输入 #1
5.0 9.0 5.0 2.5 1.8 5输出 #1
1说明/提示
当球落入车的尾部时，算作落入车内。
【题目来源】
NOIP 2002 提高组第三题
解题思路
本题核心是通过物理公式推导+区间范围判断统计小车可接收的小球数：首先根据自由落体公式d = 0.5 × g × t 2 d=0.5×g×t²d=0.5×g×t2（g = 10 g=10g=10），推导小球落到小车顶部（高度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×V+L（小车有效水平范围）；最后统计该区间内且0 ≤ i < n 0≤i<n0≤i<n的小球数量，即为答案。该方法通过数学公式直接计算区间边界，无需遍历所有小球，时间复杂度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）。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vt;typedefpair<ll,ll>pll;constll N=1e5+10;constll mod=1e9+7;constll INF=1e18;intmain(){ll n;doubleh,s1,v,l,k;cin>>h>>s1>>v>>l>>k>>n;doublet_max=sqrt(h/5);doublet_min=sqrt((h-k)/5);ll b=ll(s1-t_min*v+l),e=ll(s1-t_max*v);b=min(b,n);e=max(e,0ll);cout<<b-e<<endl;return0;}