PKU3104 Drying

問題はこちら　3104 -- Drying．

k = 1 のときは自然乾燥と同じなので，a₀ 〜 a_n-1 の中で最大のものが答えになる．

k > 1 のときは，全部の服を乾かすのに必要な最小時間を二分探索で求める．

a_i を x 分で0にするのに必要な，乾燥機の使用時間を t_i とおく．
乾燥機によって減らされる水分量は k ・ t_i ．
自然乾燥で減る水分量は x - t_i ．
この2つの和が a_i 以上であれば良いので　k ・ t_i + x - t_i >= a_i ．
これより　t_i >= (a_i - x) / (k - 1)　が得られる．

次に，a₀ 〜 a_n-1 全部を x 分で乾かすための条件を考える．
乾燥機は1度に1つの服しか乾かせないので全部の服を x 分で乾かすための乾燥機の使用時間は，合計で t₀ + t₁ + … + t_n-1 分になる．
これが x 以下であれば全部の服を x 分で乾かすことができる．

具体例 a = { 6, 13, 17 } , k = 5 でみてみる．
x = 10 のとき
t₀ = 0
t₁ = 1
t₂ = 2

余裕で間に合う．

x = 5 のとき
t₀ = 1
t₁ = 2
t₂ = 3

それぞれを5分で乾かそうとすると，乾燥機を6分使うことになるから無理．

#include <cstdio>
#include <algorithm>
using namespace std;
int a[100010],n,k;
bool ok(int x)
{
    long long sum=0;
    for (int i=0;i<n;++i) if (a[i]>=x) {
        int t=(a[i]-x+k-2)/(k-1);
        sum+=t;
    }
    return sum<=x;
}
int main()
{
    scanf("%d",&n);
    for (int i=0;i<n;++i) scanf("%d",a+i);
    scanf("%d",&k);

    if (k==1) { printf("%d\n",*max_element(a,a+n)); return 0; }

    int L=0,R=1000000000;
    while (L<=R) {
        int M=(L+R)/2;
        if (ok(M)) R=M-1;
        else L=M+1;
    }
    printf("%d\n",L);
    return 0;
}