POJ 3104: Drying

概要

洗濯物がn個あって，自然乾燥だと1分間に洗濯物の水が1だけ減る．暖房機を使えば，1分間にkだけの水を減らすことができるが，これは1分間に1つの洗濯物についてだけしか使えない．
暖房機を最適に使った時，すべての洗濯物を乾かすのに必要な最小の時間はいくつか．

解法

洗濯物を乾かすために必要な時間を仮定して二分探索．

「暖房機を使えば1分間にkだけ水を減らすことができる＝自然乾燥に比べて1分間あたりk-1多く水を減らすことができる」に注意して，二分探索の判定を行う．
洗濯物iの水分量をa_iとする．時間tだけかけて洗濯物の乾燥が終わるかどうかの判定は，水分量がtより多い洗濯物iに対しceil(a_i-t/(k-1))を求め，その総和がt以下であるかどうかで行うことができる．
計算式を見ればわかるが，k=1のコーナーケースには気を付けること．

解法の勘違いとコーナーケースの見落としでWA出した．

int n, k;
ll a[100010];
bool C(ll t){
    ll sum = 0;
    for(int i = 0; i < n; ++i){
        if(a[i] > t){
            sum += (a[i] - t + k - 1) / k;
        }
    }
    return sum <= t;
}
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%lld", &a[i]);
    scanf("%d", &k);

    --k;
    ll l = 0, u = 0;
    for(int i = 0; i < n; ++i) u = max(u, a[i]);
    if(k == 0){
        printf("%lld\n", u);
        return 0;
    }
    while(u - l > 1){
        ll mid = (l + u) / 2;
        if(C(mid)){
            u = mid;
        }
        else{
            l = mid;
        }
    }
    printf("%lld\n", u);
    return 0;
}