本文主要是介绍【Codeforces Round #398 (Div. 2)】Codeforces 767B The Queue,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Finally! Vasya have come of age and that means he can finally get a
passport! To do it, he needs to visit the passport office, but it’s
not that simple. There’s only one receptionist at the passport office
and people can queue up long before it actually opens. Vasya wants to
visit the passport office tomorrow. He knows that the receptionist
starts working after ts minutes have passed after midnight and closes
after tf minutes have passed after midnight (so that (tf - 1) is the
last minute when the receptionist is still working). The receptionist
spends exactly t minutes on each person in the queue. If the
receptionist would stop working within t minutes, he stops serving
visitors (other than the one he already serves). Vasya also knows
that exactly n visitors would come tomorrow. For each visitor Vasya
knows the point of time when he would come to the passport office.
Each visitor queues up and doesn’t leave until he was served. If the
receptionist is free when a visitor comes (in particular, if the
previous visitor was just served and the queue is empty), the
receptionist begins to serve the newcomer immediately. “Reception 1”
For each visitor, the point of time when he would come to the passport
office is positive. Vasya can come to the office at the time zero
(that is, at midnight) if he needs so, but he can come to the office
only at integer points of time. If Vasya arrives at the passport
office at the same time with several other visitors, he yields to them
and stand in the queue after the last of them. Vasya wants to come at
such point of time that he will be served by the receptionist, and he
would spend the minimum possible time in the queue. Help him! Input
The first line contains three integers: the point of time when the
receptionist begins to work ts, the point of time when the
receptionist stops working tf and the time the receptionist spends on
each visitor t. The second line contains one integer n — the amount of
visitors (0 ≤ n ≤ 100 000). The third line contains positive integers
in non-decreasing order — the points of time when the visitors arrive
to the passport office. All times are set in minutes and do not exceed
1012; it is guaranteed that ts < tf. It is also guaranteed that Vasya
can arrive at the passport office at such a point of time that he
would be served by the receptionist. Output Print single non-negative
integer — the point of time when Vasya should arrive at the passport
office. If Vasya arrives at the passport office at the same time with
several other visitors, he yields to them and queues up the last. If
there are many answers, you can print any of them.
肯定要在某个人前一秒到达,到的更早没有意义,到的更晚就被他抢先了。
这样可以 O(n) 枚举一遍解决。
但是要考虑各种情况,比如在所有人之后到、别人到的时间都不在规定时间内。
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
const LL oo=1e15;
LL a[100010],ts,tf,t;
int n;
int main()
{LL now,ans,ansv=oo;scanf("%I64d%I64d%I64d%d",&ts,&tf,&t,&n);for (int i=1;i<=n;i++) scanf("%I64d",&a[i]);now=ts;if (a[1]>ts){printf("%d\n",ts);return 0;} for (int i=1;i<=n;i++){if (max(0LL,now-a[i]+1)<ansv&&a[i]-1+t<=tf){ansv=max(0LL,now-a[i]+1);ans=a[i]-1;}now=max(now,a[i])+t;}if (now+t<=tf) printf("%I64d\n",now);else printf("%I64d\n",ans);
}
这篇关于【Codeforces Round #398 (Div. 2)】Codeforces 767B The Queue的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!