Problem Description

有一臺(tái)機(jī)器，并且給你這臺(tái)機(jī)器的工作表，工作表上有n個(gè)任務(wù)，機(jī)器在ti時(shí)間執(zhí)行第i個(gè)任務(wù)，1秒即可完成1個(gè)任務(wù)。
有m個(gè)詢問(wèn)，每個(gè)詢問(wèn)有一個(gè)數(shù)字q，表示如果在q時(shí)間有一個(gè)工作表之外的任務(wù)請(qǐng)求，請(qǐng)計(jì)算何時(shí)這個(gè)任務(wù)才能被執(zhí)行。
機(jī)器總是按照工作表執(zhí)行，當(dāng)機(jī)器空閑時(shí)立即執(zhí)行工作表之外的任務(wù)請(qǐng)求。

Input

輸入的第一行包含一個(gè)整數(shù)T， 表示一共有T組測(cè)試數(shù)據(jù)。
對(duì)于每組測(cè)試數(shù)據(jù)：
第一行是兩個(gè)數(shù)字n, m，表示工作表里面有n個(gè)任務(wù), 有m個(gè)詢問(wèn)；
第二行是n個(gè)不同的數(shù)字t1, t2, t3....tn，表示機(jī)器在ti時(shí)間執(zhí)行第i個(gè)任務(wù)。
接下來(lái)m行，每一行有一個(gè)數(shù)字q，表示在q時(shí)間有一個(gè)工作表之外的任務(wù)請(qǐng)求。
特別提醒：m個(gè)詢問(wèn)之間是無(wú)關(guān)的。
[Technical Specification]
1. T <= 50
2. 1 <= n, m <= 10^5
3. 1 <= ti <= 2*10^5, 1 <= i <= n
4. 1 <= q <= 2*10^5

Output

對(duì)于每一個(gè)詢問(wèn)，請(qǐng)計(jì)算并輸出該任務(wù)何時(shí)才能被執(zhí)行，每個(gè)詢問(wèn)輸出一行。

Sample Input

1 5 5 1 2 3 5 6 1 2 3 4 5

Sample Output

4 4 4 4 7 解題思路：題意說(shuō)得很清楚了，注意m個(gè)詢問(wèn)之間是無(wú)關(guān)的。做法：預(yù)處理打表O(n)，O(1)的詢問(wèn)，從后往前暴力枚舉，如果當(dāng)前時(shí)間點(diǎn)i沒(méi)有被占用，那么就設(shè)置now為i，并且每次將時(shí)間點(diǎn)b[i]設(shè)置成now，表示目前在i時(shí)間有另外的任務(wù)請(qǐng)求對(duì)應(yīng)需要在now這個(gè)時(shí)間點(diǎn)才被執(zhí)行。 AC代碼： 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=200005; 4 int t,n,m,x,q,now,b[maxn];bool a[maxn]; 5 int main(){ 6 while(~scanf("%d",&t)){ 7 while(t--){ 8 scanf("%d%d",&n,&m); 9 memset(a,false,sizeof(a)); 10 memset(b,0,sizeof(b)); 11 for(int i=1;i<=n;++i){scanf("%d",&x);a[x]=true;} 12 for(int i=maxn-5;i>0;--i){//從后往前枚舉，如果該時(shí)間點(diǎn)沒(méi)有占用，則直接用now這個(gè)時(shí)間 13 if(!a[i])now=i;//更換沒(méi)有占用的最小時(shí)間 14 b[i]=now;//每一個(gè)任務(wù)只能延遲做 15 } 16 while(m--){ 17 scanf("%d",&q); 18 printf("%d\n",b[q]); 19 } 20 } 21 } 22 return 0; 23 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/acgoto/p/9508837.html

總結(jié)

以上是生活随笔為你收集整理的题解报告：hdu 4907 Task schedule的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。