題意:

n個人排隊去辦理通行證,給出辦公室開始辦理的時間s和停止辦理的時間d,以及辦理一個人的通行證需要花費的時間t,小明也想去辦理通行證,在知道n個人都是什么時間(a[i])來的情況下,小明想知道自己什么時候去自己能夠辦理到通行證且等待的時間最少,另外小明如果和別人同時到,他會排在這個人后面

思路:

模擬.

我們模擬經(jīng)過第i個人后,辦公室要在什么時間才能辦理,用變量記錄,一開始就是s,之后只要tim=max(tim, a[i])+t這樣去更新就行,我們枚舉小明在a[i]-1,這個時間點到,看需要花費多少時間,所花費的時間即為tim-a[i]+1(如果是負數(shù),沒關(guān)系,題目只要求輸出什么時候到達就行,所以負數(shù)和0的效果是一樣的),每次去更新下就行.最后check一下是不是tim+t<=d,也就是說是不是所有人辦理完后還足夠辦理一次.另外我們在枚舉的時候要把a[i]>=d的變量跳過.

所以這里最重要的是明白我們只需要枚舉a[i]-1就可以,然后明白怎么更新辦公室閑置的時間,以及花費的時間怎么求.

代碼:

#include <bits/stdc++.h>using namespace std;const int maxn=1e5+5;long long a[maxn];struct p{     long long tim;     long long cost;}b[maxn];bool cmp(p a, p b){	return a.cost<b.cost;}int main(){    long long s, d, t;    int n;    cin>>s>>d>>t>>n;     int i, j;    for(i=0; i<n; i++)    {	scanf("%lld", &a[i]);    }    long long tim=s;    int top=0;    for(i=0; i<n; i++)    {	if(a[i]>=d)continue;	b[top].cost=tim-a[i]+1;	b[top++].tim=a[i]-1;      tim=max(tim, a[i])+t;      if(d-tim+1<t)break;    }    if(d-tim>=t)return 0*PRintf("%lld/n", tim);    sort(b, b+top, cmp);    printf("%lld/n", b[0].tim);}