05 August 2008
有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。
给一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。
每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到 队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。
返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。
为了计算第 k 个人买完票所需的时间，我们可以首先计算在这个过程中每个人买票所需要的时间，再对这些时间求和得到答案。
我们可以对每个人的下标 i 分类讨论：
如果这个人初始在第 k 个人的前方，或者这个人恰好为第 k 个人，即 i≤k，此时在第 k 个人买完票之前他最多可以购买 tickets[k] 张。考虑到他想要购买的票数，那么他买票所需时间即为 min(tickets[k],tickets[i])；
如果这个人初始在第 k 个人的后方，即 i>k，此时在第 k 个人买完票之前他最多可以购买 tickets[k]−1 张。考虑到他想要购买的票数，那么他买票所需时间即为 min(tickets[k]−1,tickets[i])。
遍历每个人的下标，按照上述方式计算并维护每个人买票所需时间之和，即可得到第 k 个人买完票所需的时间，我们返回该值作为答案。
1
2
3
4
5
6
7
8
9
class Solution {
public int timeRequiredToBuy(int[] tickets, int k) {
int result = 0;
for (int i = 0; i < tickets.length; i++) {
result += Math.min(tickets[i], i <= k ? tickets[k] : tickets[k] - 1);
}
return result;
}
}