程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bestcoder#3——Task schedule

bestcoder#3——Task schedule

編輯：C++入門知識

bestcoder#3——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

Sample Output

AC:用模擬+優先隊列做的又費事又費力還耗內存- =傷不起（水題）。

//author: svtter
//

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define INF 0xffffff
#define lln long long

using namespace std;

struct item
{
    int n;
    int i;
    bool operator < (const item &a)const
    {
        return n > a.n;
    }
};

int m, n;
int work[100001];
int extra[100001];
priority_queue  q;

int main()
{
    int i, cur;
    int t;
    int t1;
    int a;
    item it, b;
    freopen("test2", "r", stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        for(i = 0; i < n; i++)
            scanf("%d", &work[i]);
        for(i = 0; i < m; i++)
        {
            scanf("%d", &it.n);
            it.i = i;
            q.push(it);
        }
        sort(work, work+n);
        t1 = 0;
        cur = 0;
        while(!q.empty())
        {
            if(t1 != n)
                a = work[t1];
            else
            {
                while(!q.empty())
                {
                    b = q.top();
                    if(b.n <= cur)
                        extra[b.i] = cur;
                    else
                    {
                        extra[b.i] = b.n;
                    }
                    q.pop();
                }
                break;
            }
            if(!q.empty())
                b = q.top();
            else
                break;

            if(a > b.n && a != cur)
            {
                if(b.i <= cur)
                    extra[b.i] = cur;
                else
                    extra[b.i] = b.n;
                q.pop();
            }
            else
            {
                cur = work[t1]+1;
                t1++;
            }
        }

        for(i = 0; i < m; i++)
            printf("%d\n", extra[i]);
        printf("\n");
    }
    return 0;
}