题目描述
假设有一个独家活动,许多人希望参加。活动从时间0开始。对于每个参与者,你会得到一个表示他们到达事件的时间(相对于活动开始时间的秒数)。
然而,进入该活动需要进行身份验证检查,这需要一定的时间,因此人们可能需要在队列中等待进入。
具体来说,每个参与者的身份验证检查需要5分钟的时间。此外,如果一个人到达活动现场并看到队列中有超过10个人,他们将立即离开。
你的任务是返回一个整数数组,表示每个人的身份验证检查完成的时间。时间应以秒为单位,相对于活动开始时间计算。
如果一个人在到达时立即离开,那么他的身份验证检查完成时间应与到达时间相同。
注:开始身份验证检查时,队列为空。
例如,对于 times = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],]
输出应为 solution(times) = [301, 601, 901, 1201, 1501, 1801, 2101, 2401, 2701, 3001, 3301, 3601, 13, 14, 15]。
注释
1. 排队人数按等待开始身份证检查的人数计算,不包括已在进行身份证检查的人数。
2. 如果新来的人与另一个人完成身份证检查的时间相同、排队等候的第一个人应先接受身份证检查,新来的人应在队列中等候。
思路:
1.队列不是最后存放结果的地方
2.vector<int> result 需要更具队列的某种性质(队列长度)来往里添加结果
3.如何进队和出队
4.如何往 result 里添加答案
5.超过10个人代表队列里有 11 个人的时候,参与者会离开。但是队列可以有11个人(排队人数按等待开始身份证检查的人数计算,不包括已在进行身份证检查的人数。)
6.对于队列来说有点类似滑动窗口,如何收缩边界(出队)q.front() <= t
队列就是滑动窗口,可以被处理时间的统统入队(我们队列里放的是身份验证检查完成的时间)。
每次遇到新的时间,先看看是否能收缩队列的左边界。如果可以的话就腾出了位置让新的时间入队。
最后我们检查队列是否有空位可以处理新的时间,可以的处理时间入队,不行的话新的时间离开
代码
#include <bits/stdc++.h>
using namespace std;
vector<int> solution(vector<int> ×)
{
queue<int> q;
vector<int> result;
for (int t : times)
{
while (!q.empty() && q.front() <= t)
{ // 每次开始循环就把当前该去处理或者离开队伍的离队
q.pop();
}
if (q.size() <= 11)
{
int finish_time = max(t, result.empty() ? 0 : result.back()) + 300;
result.push_back(finish_time);
q.push(result.back());
}
else
{
result.push_back(t); // 大于10
}
}
return result;
}
int main()
{
vector<int> times = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 601, 602, 603, 604, 605};
vector<int> result = solution(times);
for (int res : result)
{
cout << res << " ";
}
cout << endl;
return 0;
}