[CF767B] The Queue

[CF767B] The Queue - 贪心

Description

接待员在午夜Ts分钟时开始工作，并在午夜Tf分钟后关闭。对于每个来访者，Vasya都知道他何时会来到护照办公室。每个访客排队等候，直到被服务才离开。如果Vasya和其他几个来访者同时到达护照办公室，他会向他们让步，并作为最后一名之后站在队伍中。Vasya想找到一个适合的时间，使得接待员会服务他，并且他会花费最少的时间在队伍中。

Solution

除非踩着最后一个人走了的时候进去（或者最开始），否则踩在一个人到的前一秒去一定不会更坏

枚举每个人，用他到达时刻的前一秒来试一试

我们需要维护之前的那些人完成的最晚时间，与新到达的这个人的时间 -1 取最小值，作为一个备选的时间

如果这个备选时间进去做完还没下班，我们就找到了一种方案，考虑更新答案

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int t_begin, t_end, t_serv, n;
    cin >> t_begin >> t_end >> t_serv >> n;
    int t_last = t_begin;
    int ans = 1e18;
    int ansval = 1e18;
    for (int i = 1; i <= n; i++)
    {
        int t_visitor;
        cin >> t_visitor;
        if (t_visitor + t_serv > t_end)
            break;
        if (t_last + t_serv <= t_end && t_last - t_visitor + 1 <= ansval)
        {
            ansval = t_last - t_visitor + 1;
            ans = min(t_last, t_visitor - 1);
        }
        t_last = max(t_last, t_visitor) + t_serv;
    }
    if (t_last + t_serv <= t_end)
        ans = t_last;
    cout << ans;
}