POJ 3045: Cow Acrobats

概要

牛がN匹いる．i番目の牛は重さがw[i]で，強さがs[i]であることがわかっている．
この牛でタワーをつくりたい．タワーは牛が別の牛一頭にのることを繰り返してつくられる．
この時，牛iの危険度は (牛iの上に乗っている牛の重さの合計) - (牛iの強さ) で求められる．
N匹の牛を使って作るとき，牛の危険度の最大値を最小化したい．

解法

危険度を仮定して二分探索．

調べてみると二分探索使わなくても貪欲で解けるらしい．
貪欲力が低い．．．

const ll MAX_S = 1000000100;

int N, sum;
pair<int, int> cow[50010];

bool C(ll risk){
    priority_queue<int> Q;
    int i = 0;
    int tsum = sum;
    while(i < N){
        for(; i < N && tsum - cow[i].first <= risk; ++i){
            Q.push(cow[i].second); 
        }
        if(i < N && Q.empty()) return false;
        tsum -= Q.top();
        Q.pop();
    }
    return true;
}
int main(){
    scanf("%d", &N);
    sum = 0;
    for(int i = 0; i < N; ++i){
        int w, s;
        scanf("%d%d", &w, &s);
        cow[i] = make_pair(s + w, w);
        sum += w;
    }
    sort(cow, cow + N);
    reverse(cow, cow + N);
    ll lb = -MAX_S, ub = MAX_S;
    while(ub - lb > 1){
        ll mid = (ub + lb) / 2;
        if(C(mid)){
            ub = mid;
        }
        else{
            lb = mid;
        }
    }
    printf("%lld\n", ub);
    return 0;
}