Drying (Poj3104,Northeastern Europe 2005, Northern Subregion)

ACチャネル:http://poj.org/problem?id=3104
Drying
Description
今、n枚の服があります.服ごとに水滴の数を教えてあげます.時間単位ごとに、服は自然に乾かされて水滴が1滴滴ります.
オーブンを1つ(1つだけ)使うこともできます.各時間単位で、このオーブンは1枚の服(1枚しかない)にk滴の水滴を減らすことができる.オーブンを使用すると、この時間単位では、この服は自然に乾かない.
今、オーブンを合理的に使って、すべての服を乾かす時間を最短にしなければなりません.(各時間単位で、オーブンでは服を1枚しか焼いていません)
Input
1行目は、服の件数を表す整数nを含む.2行目は、各服の水滴の数を表すスペースで区切られたn個の整数を含む.3行目は、オーブンの効率、すなわち、服の水滴数を時間単位で減少させることができる整数kを含む.
Output
最も短い時間を表す整数は1つしかありません.
Sample Input 1
3 2 3 9 5
Sample Output 1
2
Sample Input 2
3 2 3 6 5
Sample output 2
2
HINT
100%のデータに対して、1≦n≦105であり、衣類上の水滴数は109以下の正の整数であり、1≦k≦109である.
Solution
この問題は,第一の感覚は貪欲である.
各時間を列挙し、水滴数が最大の服をオーブンで使用します.最大水滴数が0の場合、現在の時間が出力されます.明らかにタイムアウトします.最悪の場合、最大時間は109に達します.
だから2点です.最適化問題を判定問題に変換しました
現在判断する時間をt,衣服iについて水滴数をsiとする.明らかに、私たちが判断しなければならないのは、ストーブが足りないことです.
では、si≦tであれば、この服はオーブンを使用する必要がないので、直接無視することができます.
si>tであれば、自然に風が乾くと、オーブンを使用する時間をt 0とすると、t 0∗k+(t−t 0)≧si⇒t 0∗(k−1)≧si−t⇒t 0≧(si−t)/(k−1)
オーブンをできるだけ少なく使用するためには、t 0は(si−t)/(k−1)上向きに整列した結果をとる.なお、k=1の場合、上記の式ではエラーが発生するので、特判します.
すべての服を遍歴し、すべてのt 0(オーブンを使用する必要がある服)の和を求める.これとtより大きいと、t時間内にすべての服を乾かすことはできません.
アルゴリズムの全複雑度はO(nlogTmax)である.
注意long long .
Code

#include <iostream>
#include <cstdio>

using namespace std;

long long n,la,l=1,r,ans;
long long s[100010];

inline long long Max(long long a,long long b){
    return a>b?a:b;
}

bool pan(long long t){
    long long ti=0;
    for(long long i=1;i<=n;i++){
        if(s[i]>t){
            if((s[i]-t)%(la-1))
                ti+=(s[i]-t)/(la-1)+1;
            else ti+=(s[i]-t)/(la-1); 
            if(ti>t)return false;
        }
    }
    return true;
}

int main(){
    scanf("%I64d",&n);
    for(long long i=1;i<=n;i++){
        scanf("%I64d",&s[i]);
        r=Max(r,s[i]);
    }
    scanf("%I64d",&la);
    if(la==1){printf("%I64d
",r);return 0;}
    ans=r;
    while(l<=r){
        long long mid=(l+r)/2;
        bool flag=pan(mid);
        if(flag){
            if(ans>mid)ans=mid;
            if(r!=mid-1)r=mid-1;
            else break; 
        }
        else{
            if(l!=mid+1)l=mid+1;
            else break; 
        }
    }
    printf("%I64d
",ans);
    return 0;
}