Leetcode 2073. 买票需要的时间

一、题目描述

有 $n$ 个人前来排队买票，其中第 $0$ 人站在队伍 最前方，第 $(n - 1)$ 人站在队伍 最后方 。
给你一个下标从 $0$ 开始的整数数组 tickets，数组长度为 $n$ ，其中第 $i$ 人想要购买的票数为 tickets[i]。
每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到 队尾 重新排队（瞬间发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开队伍。
返回位于位置 $k$（下标从 0 开始）的人完成买票需要的时间（以秒为单位）
输入：tickets = [2,3,2], k = 2
输出：6
解释：
第一轮，队伍中的每个人都买到一张票，队伍变为 [1, 2, 1]。
第二轮，队伍中的每个都又都买到一张票，队伍变为[0, 1, 0]。位置 2 的人成功买到 2 张票，用掉 $3$ + $3$ = $6$ 秒。
来源：Leetcode 2073. 买票需要的时间

二、解题报告

1、思路分析

(1) 符合先进先出，应用队列。
(2) 用一个结构体数组储存每个人所需的票数，和序号。
(3)一个for循环使所有人入队。
(4)使队头出队，并减少其需要的票数，时间增加。
(5)判断出队的人所需票数是否为0，若为否，重新加入队尾。
(6)若是0，则判断其序号是否是指定人序号，若是返回

2、代码详解

typedef struct {
    int idx;
    int need;
}que;
int timeRequiredToBuy(int* tickets, int ticketsSize, int k){
    que q[100000],tmp;
    int time=0;
    int front=0,rear=0;
    for(int i=0;i<ticketsSize;i++){
        q[rear].idx=i;
        q[rear].need=tickets[i];
        ++rear;
    }
    while(front<rear){
        tmp=q[front++];
        tmp.need--;
        time++;
        if(tmp.need){
            q[rear++]=tmp;
        }else{
            if(tmp.idx==k){
                return time;
            }
        }
    }
    return time;
}

借鉴：英雄哪里出来

打赏