HDU 4907 BestCoder3_1 Task schedule

Task schedule

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0


Problem Description

有一台機器，並且給你這台機器的工作表，工作表上有n個任務，機器在ti時間執行第i個任務，1秒即可完成1個任務。
有m個詢問，每個詢問有一個數字q，表示如果在q時間有一個工作表之外的任務請求，請計算何時這個任務才能被執行。
機器總是按照工作表執行，當機器空閒時立即執行工作表之外的任務請求。

Input

輸入的第一行包含一個整數T， 表示一共有T組測試數據。

對於每組測試數據：
第一行是兩個數字n, m，表示工作表裡面有n個任務, 有m個詢問；
第二行是n個不同的數字t1, t2, t3....tn，表示機器在ti時間執行第i個任務。
接下來m行，每一行有一個數字q，表示在q時間有一個工作表之外的任務請求。

特別提醒：m個詢問之間是無關的。

[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

對於每一個詢問，請計算並輸出該任務何時才能被執行，每個詢問輸出一行。

Sample Input

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

Sample Output

4
4
4
4
7
//從前往後直接暴力會超時
#include
#include
using namespace std;
const int N = 2e5 + 10;
int busy[N], ans[N], m, n, t, cas, q;
int main()
{
    scanf ("%d", &cas);
    while (cas--)
    {
        scanf ("%d%d", &n, &m);
        memset (busy, 0, sizeof (busy));
        for (int i = 1; i <= n; ++i)
            scanf ("%d", &t), busy[t] = 1;
        ans[200001] = 200001;
        for (int i = 200000; i >= 1; --i)
            if (busy[i]) ans[i] = ans[i + 1];
            else ans[i] = i;
        while (m--)
            scanf ("%d", &q), printf ("%d\n", ans[q]);
    }
    return 0;
}