Drying POJ – 3104(二分)有坑

It is very hard to wash and especially to dry clothes in winter. But Jane is a very smart girl. She is not afraid of this boring process. Jane has decided to use a radiator to make drying faster. But the radiator is small, so it can hold only one thing at a time.

Jane wants to perform drying in the minimal possible time. She asked you to write a program that will calculate the minimal time for a given set of clothes.

There are n clothes Jane has just washed. Each of them took ai water during washing. Every minute the amount of water contained in each thing decreases by one (of course, only if the thing is not completely dry yet). When amount of water contained becomes zero the cloth becomes dry and is ready to be packed.

Every minute Jane can select one thing to dry on the radiator. The radiator is very hot, so the amount of water in this thing decreases by k this minute (but not less than zero — if the thing contains less than k water, the resulting amount of water will be zero).

The task is to minimize the total time of drying by means of using the radiator effectively. The drying process ends when all the clothes are dry.

Input
The first line contains a single integer n (1 ≤ n ≤ 100 000). The second line contains ai separated by spaces (1 ≤ ai ≤ 109). The third line contains k (1 ≤ k ≤ 109).

Output
Output a single integer — the minimal possible number of minutes required to dry all clothes.

Sample Input
sample input #1
3
2 3 9
5

sample input #2
3
2 3 6
5
Sample Output
sample output #1
3

sample output #2
2

题意
题意非常简单　就是说我们有一堆衣服　这些衣服有分别的水分　水分有两种减少方式　一种是每分钟自然减一　或者使用散热器散热　这样就无法加上自然减少的一点了　要求我们寻找最少晾干所有衣服的天数

解决
首先这道题刚开始的时候我们会发现N的数量并不大　而且我们很好验证一个天数我们是否能晾干衣服　时间复杂度为N 这就意味着我们很好写出Check函数　然后这题就是一个很明显的二分答案了　因为Check函数的N复杂度　所以整体的复杂度为N*log(sum_for_day) 是一个不错的时间复杂度　但是我们的这道题在Check中用到了除法　有一种情况就是除法分母为零　这样就会导致程序抛出异常　而我们又没有一个catch语句块　所以程序调用terminate终止程序　这也就是为什么会出现RE的原因　所以这也警告我们注意边界条件

AC代码

```cpp
#include<cstdio>
#include<cstring>
#include<cmath>
#include<set>
#include<cstdlib>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

namespace{
    typedef long long ll;
    ll m,n;
    ll book[100000+10];
    ll Left,Right;
    ll ans,flag;

    bool Check(ll mid){
        ans = 0;
        if(n==1){ //防止n为零　会整除零　抛出错误
            for(int i=1;i<=m;++i){
                if(book[i] > mid){
                    return false;
                }
            }
            return true;
        }
        for(int i=1;i<=m;++i){
            if(book[i]-mid>0){
                ans+=((book[i]-mid)%(n-1)?(book[i]-mid)/(n-1)+1:(book[i]-mid)/(n-1));
            }
        }
        //可以利用烘干机完成除去随时间减少的水分返回true
        if(ans>mid) return false;
        else return true;
    }
}

int main(){
    scanf("%lld",&m);
    for(int i=1;i<=m;++i){
        scanf("%lld",&book[i]);
    }
    scanf("%lld",&n);
    Left = 1;Right = 1e9;
    while(Left<=Right){
        int mid = Left + ((Right - Left) / 2);
        if(!Check(mid)){
            Left = mid+1;
        }else{
            flag = mid;
            Right = mid-1;
        }
    } 
    cout << flag << endl;
    return 0;
}