A 曹老师的金句

题目链接：https://ac.nowcoder.com/acm/contest/94570/A

现在有同学需要这些金句，于是曹老师找孙老师和廖老师帮忙分发，但他们同时只有一个人参与分发。

现在有同学前来排队领取，其中第 0 个人站在队伍 最前方，第 n-1 人站在队伍 最后方。

给定一个从 0 开始的整数数组 tickets，其长度为 n，其中第 i 个人想要领取的数量为 tickets[i]。

每个人领取需要花费 1 秒。每个人一次只能领取 一份，如果需要领取更多的，他必须走到 队尾 重新排队（瞬间发生，不计时间）。如果一个人没有剩下需要领取的，那么他将会从队伍中消失。

请计算位于位置 k 的人完成领取所需的时间（以秒为单位）。

解析：

题中要求第k个同学取完票的时间，根据题意，我们可以得到：

第 i 次取到第 k 个同学取票时，该同学前面的同学都取了 i 次票，该同学后面的同学都取了 i-1 次票。因此，我们可以直接计算出第 k 个同学最后一次取票时的时间。

因此我们可以得到

for(int i = 0;i<n;i++)
{
  	if(i<=k)
		time+=tickets[k];
	else
    	time+=tickets[k] - 1;
}

在题目中，我们会发现，有部分同学取完票之后不会再进行排队，因此，我们要判断那一部分同学拿了多少票，因此，代码更新为

for(int i = 0;i<n;i++)
{
    if(i<=k)
        if(tickets[i] <= tickets[k]) time+=tickets[i];
        else time+=tickets[k];
    else
        if(tickets[i] < tickets[k]) time+=tickets[i];
        else time += tickets[k]-1;
}

特别需要注意的是：

题目中的数据范围为，其中 n * tickets = 1e10，超过了int的范围，因此，应该用long long

n == tickets.length
1 <= n <= 10000
1 <= tickets[i] <= 1e6
0 <= k < n

代码：


#include <iostream>
using namespace std;
const int N = 1e4+10;
int q[N],res[N];
int main(){
    int n;
    cin>>n;
    for(int i = 0;i<n;i++)
    {
        cin>>q[i];
    }
    long long time = 0;
    int k;
    cin>>k;
    for(int i = 0;i<n;i++)
    {
        if(i<=k)
            if(q[i] <= q[k]) time+=q[i];
            else time+=q[k];
        else
            if(q[i] < q[k]) time+=q[i];
            else time += q[k]-1;
    }
     
    cout<<time;
    return 0;
}