Task schedule

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
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<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int maxn = 100005; int n,q,m,time[maxn]; int fa[maxn<<1];int find(int x) {if(fa[x] == x) return x;return fa[x] = find(fa[x]); }int main() {int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++)scanf("%d",&time[i]);sort(time+1,time+1+n);for(int i = 1; i <= 200005; i++) fa[i] = i;for(int i = n; i >= 1; i--){int f = find(time[i] + 1);fa[time[i]] = f;}while(m--){scanf("%d",&q);printf("%d\n",find(q));}}return 0; }

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的hdu 4907(并查集)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。