UVA 1422 Processor ( 二分搜 + 置點問題 )

UVa Online Judge
馬上會想到二分搜最大速度，而判斷的部分就會變成經典的置點問題。每個點 ( 作業 )都有左界和右界，只能將它置於其中。一個經典的算法是先將每個點以其左界限制做排序，然後由左到右依次考慮每個位置該放置哪個點，這部分可以利用優先佇列，每次將佇列裡右界最小的取出來做掉。如果把該位置的資源用盡後作業仍然有剩，則更新剩餘的工作量後再丟進去一次。如果在過程中優先佇列取出來的點的右界已過期，或者迴圈結束後有任何點還沒考慮過，或者還在優先佇列裡沒有出來，則判斷無解。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 4;
const int MAXRD = 2e4 + 4;
const int MAXW = 1e3 + 3;

struct Work{
    int r, d, w;
    Work(){}
    void read(){
        scanf("%d%d%d", &r, &d, &w);
    }
    bool operator < (const Work &oth) const{
        return d > oth.d;
    } // pq get least d
} work[MAXN];

bool cmp_l(const Work &a, const Work &b){
    return a.r < b.r;
}

int n;

bool ok(int x){
    priority_queue<Work> pq;
    int k = 0;
    for(int i = 1; i <= MAXRD; ++i){
        while( work[ k ].r < i && k < n ) pq.push( work[ k++ ] );
        int space = x;
        while( space > 0 && !pq.empty() ){
            Work c = pq.top(); pq.pop();
            if( c.d < i ) return false;
            if( c.w <= space ) space -= c.w;
            else{
                c.w -= space;
                space = 0;
                pq.push( c );
            }
        }
    }
    if( k == n && pq.empty() ) return true;
    return false;
}

void solve(){
    sort( work, work + n, cmp_l );    
    int lb = 1, rb = MAXN * MAXW;
    int ans = -1;
    while( lb <= rb ){
        int mid = ( lb + rb ) / 2;
        if( ok( mid ) ) ans = mid, rb = mid - 1;
        else lb = mid + 1;
    }
    assert( ans >= 0 );
    printf("%d\n", ans);
}

int main(){
    int T; scanf("%d", &T);
    while( T-- ){
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            work[ i ].read();
        solve();
    }
    return 0;
}