1851 · 购买通行证

描述

亚历克斯计划参观博物馆,并在柜台购买相同的通行证。管理员决定不出售团体通行证,一次只提供一张通行证。如果访客需要一张以上的通行证,他/她必须再次重新排队到柜台并购买下一张通行证。亚历克斯想购买许多通行证。访客顺序和每位访客需要的通行证数量是已知的,亚历克斯需要多少时间才能买到所有的通行证?Alex在队列中的位置将被给定,每次交易需要1个时间单位。可以忽略每次转到行后面所需的时间。

|arr|<=100000 arr[i]<=10000

样例

样例 1:

输入:
arr=[1,2,5],k=1
输出:
4
解释:
有3个人 0,1,2 在排队。亚历克斯的编号是1
第一个时间点,队列为0(1)<-1(2)<-2(5),编号0获得门票。
第二个时间点,队列为1(2)<-2(5) 亚克斯获得门票,并返回队伍最末端
第三个时间点,队列为2(5)<-1(1) 编号2获得门票,并返回队伍最末端
第四个时间点,队列为1(1)<-2(4) 亚克斯获得门票,他已经买到了所需要的所有门票

样例 2:

输入:
arr=[3,2,1], k = 0,
输出:
6
class Solution:
    """
    @param arr: the line 
    @param k: Alex place
    @return: the time when Alex requires to buy all passes
    """
    def buyPasses(self, arr, k):
        # Write your code here.
        count = 0
        i = 0
        length = len(arr)
        while True:
            if arr[k] == 0:
                return count

            if arr[i] != 0:  # != 0, 此时才需要时间。=0跳过
                arr[i] -= 1
                count += 1

            i += 1
            if i == length:
                i = 0

执行结果: Time Limit Exceeded 
 

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注