Funcia
Lv.1mathqueuesimulation

Ticket Line

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

n people stand in a line at a ticket booth; person 0 is at the front and person i wants tickets[i] tickets. Every second the booth sells one ticket to the person at the front. That person then goes to the back of the line if they still need more, or leaves otherwise (moving takes no time). Return how many seconds pass until person k has bought all of their tickets.

Examples

ticketskresult
[2, 3, 2]26
[5, 1, 1, 1]08
[1]01

Example 2 — person 0 buys one ticket, the other three buy one each and leave, then person 0 buys the remaining four: 8 seconds.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(tickets: int[], k: int) → long

Constraints

  • 1≤1 \le tickets.length ≤200,000\le 200{,}000
  • 1≤1 \le tickets[i] ≤109\le 10^9
  • 0≤0 \le k << tickets.length
  • The answer may exceed the 32-bit range.

Expected complexity

Time
O(N)
Space
O(1)

Examples

ticketskExpected
[2,3,2]26
[5,1,1,1]08
[1]01

Hint

Hint

The line moves in rounds, and person k finishes in round tickets[k]. Up to then, everyone at or before k buys min(tickets[i], tickets[k]) tickets and everyone after k buys min(tickets[i], tickets[k] - 1), one second per ticket; the sum is the answer, in O(N)O(N). Simulating second by second takes as many steps as the answer (up to about 101410^{14}) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.