Drying POJ3104

投稿日：2022/09/12 更新日:2022/09/12

問題

$N$ 枚の服があります。 $i$ 番目の服は $a_i$ の量の水を含んでいます。これから服を乾かします。乾燥機を使わない場合は毎分1だけ含んでいる水の量は減っていきます。乾燥機を使う場合、1分で $k$ だけ水の量を減らせます。乾燥機は1台のみで1回につき1枚しか使えません。全ての服を乾かすのに最短で何分かかるでしょう。

水の量は0を未満にはなりません。

解法

$x$ 分以内で乾かせるかを2分探索します。

$a_i <= x$ の場合は乾燥機を使う必要はありません。

$a_i > x$ の場合、乾燥機を使う必要があります。乾燥機を1回使うことによって、かかる時間を $k-1$ 分短縮することができます。前提条件より、乾燥機は同時に使えないため、使う回数だけ時間を要旨ます。つまり、 $x$ 回以上使う場合は $x$ 分以内に全ての服を乾かすことは出来ません。

乾燥機を使う回数は以下の式で求まります。 $a_i > x$ の時。

\left\lceil \frac{a_i - x}{k-1} \right\rceil

$k-1$ で割るので $k=1$ の時のみ別の処理を書かなければなりません。

実装

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0;i < n; ++i){
        cin >> a[i];
    }
    int k;
    cin >> k;

    if(k == 1){
        int ans = 0;
        for(int i = 0;i < n; ++i){
            ans = max(ans, a[i]);
        }
        cout << ans << endl;
        return 0;
    }

    int ok = 1e9, ng = 0;
    while(ok - ng > 1){
        int mid = (ok + ng)/2;

        long long count = 0;
        for(int i = 0;i < n; ++i){
            if(a[i] <= mid)continue;
            count += (a[i] - mid + (k-2)) / (k-1);
        }

        if(count <= mid){
            ok = mid;
        }else{
            ng = mid;
        }
    }

    cout << ok << endl;

    return 0;
}