学步园

题意：有n个衣服，告诉你每件衣服的水份，每秒减一，有一个烘干机每秒能给一个衣服减k的水份，问最少要多少时间把衣服全部晾干。

二分答案，然后判断正确性，设第 i 件衣服有a[ i ]的水份，对于二分的答案mid，如果a[ i ]  < = mid ，自然风干就行了，如果a[ i ] > mid，设它自然风干时间为t1，用机器耗时t2，则有 t1 + t2 = mid 、 t1 + t2 * k >= a[ i ]，联立得 t2 >= (a[ i ] - mid) / (k - 1)，再把所有a[ i ] > mid 的时间加起来和 mid 比较。

如果mid 能满足条件，还要看mid - 1是否满足，以得到最优解。

#include<cstring>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#define PI acos(-1.0)
using namespace std;
#define MAXN 100005

int n,k;
int a[MAXN];
int maxm,sum;
bool check(int mid){
    int i;
    double m = 0;
    for(i=0;i<n;i++){
        if(a[i] > mid){
            m += ceil(double((a[i] - mid))/double((k - 1)));
        }
    }
    if(m <= mid)    return true;
    else    return false;
}
void solve(){
    int l = 0;
    int r = maxm;
    int mid = (l+r) >> 1;
    while(l<=r){
        if(check(mid)){
            if(!check(mid-1)){
                sum = mid;
                return ;
            }
            r = mid - 1;
        }
        else    l = mid + 1;
        mid = (l + r) >> 1;
    }
}
int main(){
    int i;
    maxm = sum = 0;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
        if(a[i]>maxm)   maxm = a[i];
    }
    scanf("%d",&k);
    if(k==1)    printf("%d\n",maxm);
    else{
        solve();
        printf("%d\n",sum);
    }
    return 0;
}