An airfield's runway edge is lined with n numbered beacon lights, each currently burning at a known intensity. Aviation ground-safety rules require that in every group of 3 consecutive beacons along the line, at least one beacon's intensity is at or above a mandated minimum intensity k. A maintenance crew can raise any single beacon's intensity by exactly 1 unit with one work order, and may issue as many work orders as needed on any beacons in any order (a beacon may receive multiple work orders, and its intensity is never decreased). Determine the minimum total number of work orders required so that every window of 3 consecutive beacons contains at least one beacon whose intensity is at least k.
A single integer: the minimum total number of work orders required.
Example 1
Input
3 5 1 2 3
Expected
2
Explanation
With only 3 beacons, the single window (all three) must contain a beacon at intensity >= 5. Raising the third beacon (currently 3) needs only 2 work orders to reach 5, cheaper than raising the first (needs 4) or the second (needs 3), so the minimum is 2.
Example 2
Input
6 2 1 1 1 1 1 1
Expected
2
Explanation
All six beacons start at intensity 1 and k=2. Raising the beacons at positions 2 and 5 (0-indexed) by 1 work order each brings both to intensity 2. Every one of the four overlapping windows of size 3 — (0,1,2), (1,2,3), (2,3,4), (3,4,5) — then contains position 2 or position 5, so 2 work orders suffice, and no single work order could cover all four windows alone.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →