codeforces] #398(Div.2) B. The Queue [模擬]

2019-11-08 02:36:40

字體：大中小

供稿：網(wǎng)友

鏈接：Codeforces Round #398 (Div. 2) B. The Queue

題意

Vasya 這個(gè)人終于成年了。有一天，他想去辦個(gè)護(hù)照~~（年齡到了就想出去浪）~~。說(shuō)做咱就做，他決定明天就去辦事處搞點(diǎn)事情。

但是問(wèn)題就出現(xiàn)了，辦證這種事情一看就會(huì)有很多人，哪個(gè)時(shí)候去可以少排一會(huì)兒隊(duì)呢？

Vasya決定將偷懶進(jìn)行到底，先是弄來(lái)了辦事處的開(kāi)門(mén)時(shí)間 ts $t_s$ ，關(guān)門(mén)時(shí)間 tf $t_f$ 和為每個(gè)客戶服務(wù)需要消耗的時(shí)間 et $e_t$ （這里假設(shè)每個(gè)客戶需要的時(shí)間相同）。然后他又通過(guò)特殊渠道得知了明天會(huì)有 n $n$ 個(gè)客戶，以及每個(gè)客戶來(lái)的具體時(shí)間 nt $n_t$

補(bǔ)充：

Vasya和其他客戶到達(dá)辦事處的時(shí)間點(diǎn)均為整點(diǎn)。當(dāng)Vasya和其他人同時(shí)到達(dá)時(shí)，Vasya會(huì)表現(xiàn)出他的紳士風(fēng)度，讓其他人排在他前面工作人員反應(yīng)很快，一旦有人來(lái)就會(huì)馬上開(kāi)始工作如果給的數(shù)據(jù)有多個(gè)答案，只需給出其中任意一個(gè)答案Vasya在明天必須拿到護(hù)照

分析

題意描述應(yīng)該非常清晰了，但這個(gè)題目里面所包含的各種特殊情況在比賽的時(shí)候不是那么容易考慮得到。所有的情況大概有以下幾點(diǎn)：

來(lái)的人不是很多或者工作效率很高，在整個(gè)工作時(shí)間內(nèi)有那么一個(gè)時(shí)刻工作人員在玩手機(jī)辦事處還沒(méi)開(kāi)門(mén)，但早就有圍觀群眾到場(chǎng)了雖然來(lái)了很多人，但是大家都睡過(guò)了頭，在關(guān)門(mén)之后才到人滿為患，這一天都有很多人沒(méi)能辦成功的

1 和 3 應(yīng)該是比較簡(jiǎn)單的，直接找一個(gè)空閑的時(shí)間作為答案就可以了。相比較而言比較麻煩的是 2 和 4 。 2 和 4 需要在各個(gè)客戶之間的時(shí)間進(jìn)行比較判斷，才能尋得最優(yōu)解。當(dāng)然這四個(gè)都不是難的，結(jié)合起來(lái)更麻煩。

下面就說(shuō)一下我的思路：

最優(yōu)解就在 空閑時(shí)間 和 某個(gè)客戶來(lái)之前一分鐘的那個(gè)時(shí)間（nt?1 $n_t-1$ ） 其中一個(gè)。

空閑時(shí)間就不解釋了。根本不用等啊。（但是一定要保證到關(guān)門(mén)之前有充足的時(shí)間來(lái)辦護(hù)照哦，即t+et<tf $t+e_t<t_f$ ）

后面那個(gè)的話就是

把本來(lái)可以排最少時(shí)間的客戶擠掉，代替他的位置。（這樣你就必須比他早來(lái)）盡可能地不在前面的人身上浪費(fèi)時(shí)間。（只要早一分鐘來(lái)）

然后這個(gè)問(wèn)題就變成了求哪個(gè)客戶等的時(shí)間最短的問(wèn)題（分別求出他們離開(kāi)的時(shí)間就行了）（總共就106 $10^6$ 的客戶，都遍歷一遍也沒(méi)問(wèn)題）

代碼

#include <cstdio>typedef __int64 LL;LL nt[100005];int main(){ LL ts,tf,et; while(~scanf("%I64d%I64d%I64d",&ts,&tf,&et)){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%I64d",&nt[i]); } LL t=ts,ans=nt[1]-1; LL low=t-nt[1]+1; //最少消耗的時(shí)間 if(ans+et>tf){ ans=ts; t=tf+1; } int f=0; //判斷是否有空閑時(shí)間 for(int i=1;i<=n&&t<=tf;i++){ if(nt[i]>t){ ans=t; f=1; break; } if(i>1){ LL l=t-nt[i]+1; //當(dāng)前客戶消耗的時(shí)間 if(l<low){ ans=nt[i]-1; low=l; } } t+=et; } if(f) 小結(jié)

由于這個(gè)題目考慮的點(diǎn)比較多且繁瑣（在比賽的時(shí)候我真的這樣覺(jué)得！）所以就收錄下來(lái)了~~（其實(shí)是個(gè)水題）~~ 針對(duì)模擬類(lèi)的題目自己不是特別敏感，寫(xiě)一下也加深印象。

如果有更好的方法或者我有什么不足或者有什么值得探討的東西的話，可以評(píng)論或者聯(lián)系我。