[NOIP2002-提高] 自由落体

题目描述

天花板高 $H$ ，其下 $n$ 个体积不计的小球位于 $0,1,\dots,n-1$ ；地面上有长 $L$ 、高 $K$ 的小车，车头距原点 $S_1$ ，以速度 $V$ 朝原点前进。球与车同时运动，球做自由落体 $d=5t^2$ （ $g=10$ ），与车距离 $\le 0.0001$ 即算被接住，落到地面后不再能被接住，求能接住多少球。输入 $H,S_1,V,L,K,n$ （ $1 \le H,S_1,V,L,K,n \le 100000$ ，除 $n$ 外均可为小数）。样例：输入 5.0 9.0 5.0 2.5 1.8 5，输出 1。

思路

球只在高度落在车顶到地面这段时间内可能被接住，即 $t \in [t_{roof}, t_g]$ ，其中 $t_g=\sqrt{H/5}$ 、 $t_{roof}=\sqrt{\max(H-K,0)/5}$ 。这段时间里车头 $e(t)=S_1-Vt$ 连续左移，车身区间扫过的并集仍是连续一段 $[S_1-Vt_g-\varepsilon,\ S_1-Vt_{roof}+L+\varepsilon]$ ，故只需数落在这段内、编号 $0 \sim n-1$ 的整数个数。注意 $K \ge H$ 时 $t_{roof}=0$ ，取整前留一点浮点护栏。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 04:59
# update_at: 2026-10-02 04:59

import math
import sys

EPS = 1e-4    # 题目容差：球与车的水平距离不超过它就算接住
FUDGE = 1e-7  # 浮点误差护栏：整数恰好压在边界上时不算漏接


def solve() -> None:
    height, head_pos, speed, car_len, car_h, ball_num = map(float, sys.stdin.read().split())
    n = int(ball_num)

    # d = 0.5*g*t² = 5t²：球落到地面、落到车顶高度 K 各需要的时间
    t_ground = math.sqrt(height / 5)
    t_roof = math.sqrt(max(height - car_h, 0) / 5)  # K ≥ H 时球一开始就在车顶高度附近

    # 车头朝原点以速度 V 前进，t 时刻车身占据 [head_pos - Vt, head_pos - Vt + L]。
    # 球只有在 t ∈ [t_roof, t_ground]（高度夹在车顶与地面之间）才可能被接住；
    # 这段时间里滑动区间扫过的并集仍是连续一段，只需取两个端点：
    lo = head_pos - speed * t_ground - EPS   # 最晚时刻车头扫到的最左位置
    hi = head_pos - speed * t_roof + car_len + EPS  # 最早时刻车尾扫到的最右位置

    # 落在 [lo, hi] 内、编号 0..n-1 的球全部被接住，数一下整数个数
    left = max(0, math.ceil(lo - FUDGE))
    right = min(n - 1, math.floor(hi + FUDGE))
    print(max(0, right - left + 1))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 12:40
 * update_at: 2026-10-06 12:42
 */
#include <cmath>
#include <iostream>
using namespace std;

typedef long long ll;

// 题目数据与时间计算的浮点常量
const double EPS = 1e-4;    // 题目容差：球与车的水平距离不超过它就算接住
const double FUDGE = 1e-7;  // 浮点护栏：防止恰好压在边界上的整数被舍入误差挤掉
const double G_HALF = 5.0;  // 自由落体 d = 0.5*g*t^2，g = 10，故系数为 5

int main() {
    double H;   // 天花板高度
    double S1;  // 车头距原点的初始距离
    double V;   // 小车前进速度
    double L;   // 车长
    double K;   // 车高
    double n_in; // 小球个数（以浮点读入，后面取整）

    cin >> H >> S1 >> V >> L >> K >> n_in;
    ll n = n_in;

    // 球从 H 落到地面、落到车顶高度 K 分别需要的时间
    double t_ground = sqrt(H / G_HALF);
    double t_roof = sqrt(max(H - K, 0.0) / G_HALF); // K >= H 时球一开始就在车顶高度

    // 球只在 t ∈ [t_roof, t_ground] 内可能被接住；这段时间里车头 e(t) = S1 - V*t
    // 单调左移，车身区间扫过的并集仍是一段，取两个端点即可：
    double lo = S1 - V * t_ground - EPS;          // 最晚时刻车头扫到的最左位置
    double hi = S1 - V * t_roof + L + EPS;        // 最早时刻车尾扫到的最右位置

    // 编号 0..n-1 的球落在 [lo, hi] 内的全部被接住，数其中的整数个数
    ll left = ceil(lo - FUDGE);
    ll right = floor(hi + FUDGE);
    if (left < 0) left = 0;
    if (right > n - 1) right = n - 1;

    ll ans = right - left + 1;
    if (ans < 0) ans = 0;
    cout << ans << endl;

    return 0;
}