Courier Drone: Fastest Fixed-Distance Segment From Tick Logs

A delivery drone reports its progress in fixed ticks. ticks[i] is the number of meters it flew during tick i. Every tick lasts tick_seconds seconds, so tick i covers the time range [i * tick_seconds, (i + 1) * tick_seconds].

Inside a tick the drone flies at a constant speed. After t seconds of tick i it has covered ticks[i] * t / tick_seconds meters of that tick.

The operations team wants the drone's best target-meter segment: the highest average speed over any continuous time span [a, b] in which the drone covers exactly target meters. That average is target / (b - a).

def best_segment_speed(ticks: list[int], tick_seconds: float, target: int) -> float: ...

Rules:

• a and b can be any real times with 0 <= a < b <= len(ticks) * tick_seconds. A span can start or end partway through a tick.
• Ticks with 0 meters (hovering) still count toward the elapsed time of any span that contains them.
• A span can sit entirely inside one tick if that tick alone covers at least target meters.
• Answers within 1e-6 relative error are accepted.

Examples

ticks = [100, 100, 100, 100, 100], tick_seconds = 10, target = 500
answer = 10.0

The drone holds a steady 10 m/s, so every 500 m span takes 50 s.

ticks = [50, 300, 0, 250, 150], tick_seconds = 10, target = 500
answer = 17.857142857...   (= 500 / 28)

Start at t = 10 (the start of the 300 m tick). Then fly 300 m, hover for 10 s, and fly 200 of the next 250 m in 8 s. That is 28 s in total. No other span is shorter.

ticks = [20, 900, 40], tick_seconds = 10, target = 500
answer = 90.0

The middle tick alone moves at 90 m/s, so 500 m fit inside it.

Constraints

• 1 <= len(ticks) <= 10^5, 0 <= ticks[i] <= 10^5
• 1 <= target, sum(ticks) >= target
• Running totals can exceed 2^31. Use 64-bit integers in fixed-width languages.
• Aim for O(n log n) or O(n).