louisfghbvc的部落格

題目連結:  https://onlinejudge.org/external/14/1422.pdf

題目大意:  給你一些工作，每個工作有開始和截止時間，以及工作量，每單位可以做s工作量，求出最少的s就能將所有的工作做完。

思路:  這題是學校CPC競賽題，雖然有想到二分搜，不過沒想到用優先隊列。發現排程問題常常用到優先隊列。QAQ，我還是太菜了，沒解出這題。

回到正題，基本上題目想求最小工作量能做完，那就來用二分搜找答案。然後每次找的時候，我們可以每單位時間去把現在工作納入隊列，假如單位工作量不足。

表示那個工作太大可以切割，則切割放入隊列，記得單位工作量歸零。如果足夠，就把單位工作量減去當前工作量。那麼優先隊列需要考量，越早截止的應該越先被完成。

如果截止日已經比現在時間早，那麼表示這個單位量不夠。至於一個區間，舉例來說[1,3]事實上，最少一天1單位(看題目那個圖比較好理解)，所以看成[1,3)。因為區間最長時間就是2不是3

單位量不能小於0(沒意義吧...)

看代碼應該會比較清楚。

代碼:  

#include <bits/stdc++.h>
#define N 10005
using namespace std;

struct node{
    int l, r, w;
    bool operator<(node n2) const{
        return r > n2.r;
    }
}arr[N];

bool cmp(node n1, node n2){
    return n1.l < n2.l;
}

int t, n;

bool check(int s){
    priority_queue<node> pq;
    int cnt = 0;
    for(int i = 1; i <= 20000; ++i){
        while(cnt < n && arr[cnt].l == i) pq.push(arr[cnt++]);
        int res = s;
        while(pq.size() && res > 0){
            node cur = pq.top(); pq.pop();
            if(cur.r <= i) return false;
            if(res >= cur.w){
                res -= cur.w;
            }
            else{
                cur.w -= res;
                res = 0;
                pq.push(cur);
            }
        }
    }
    if(cnt == n && pq.empty()) return true;
    return false;
}

int main()
{
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 0; i < n; ++i)
            cin >> arr[i].l >> arr[i].r >> arr[i].w;
        sort(arr, arr+n, cmp);
        int l = 0, r = 1e9, ans = 0;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(check(mid)){
                ans = mid;
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }
        cout << ans << endl;
    }
}
/**
3
5
1 4 2
3 6 3
4 5 2
4 7 2
5 8 1
6
1 7 25
4 8 10
7 10 5
8 11 5
10 13 10
11 13 5
8
15 18 10
20 24 16
8 15 33
11 14 14
1 6 16
16 19 12
3 5 12
22 25 10

**/