题目链接：https://cn.vjudge.net/problem/POJ-3104

https://cn.vjudge.net/problem/16416/origin

背景

最让HSQ学长头疼的就是洗衣服了。洗完之后，每件衣服都有一定单位水分，在不使用烘干器的情况下，每件衣服每分钟自然流失1个单位水分，但如果使用了烘***则每分钟流失K个单位水分。令人遗憾是HSQ所在的宿舍楼只有1台烘***，而每台烘***同时只能烘干1件衣服,请问要想烘干N件衣服最少需要多长时间？

输入

第一行输入N，表示有N件衣服，第二行输入N件衣服的水分ai，第三行表示烘***每分钟烘干水分K
其中
1 ≤ N ≤ 100 000，1 ≤ ai ≤ 10^9,1 ≤ K≤ 10^9

输出

输出烘干N件衣服所需要的最短时间

样例输入

3
2 3 9
5

 3 2 3 6 5

样例输出

3

 2

题意：有n件衣服带有不同的水分，自然晾每分钟减少一个水分，烘***烘每分钟减少k个水分（烘***只有一个）。让你求这n个衣服全部晾干最少要几分钟。

思路：

刚开始我想每分钟过后找最大的用烘***，其余自然晾。这样每次都要遍历所有衣服一边，显然时间复杂度太高，会TLE。

但是我们可以用二分算法来降低时间复杂度，我们可以对所需要的时间二分，时间为mid时候，烘***使用时间num。num*k+mid-num=a[i]。烘***使用时间就为

ceil((a[i]-mid)*1.0/(m-1))，因为时间要是不足一分钟按一分钟计算，所以用ceil向上取整函数。还要判断一下k为1时的情况，k为1时时间就是那个含水量最大的那个的时间。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<math.h>
using namespace std;
long long  a[100005];
long long t=0;long long l,r;
int main()
{
    int n;
    long long m;
    scanf("%d",&n);
    long long int w=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        w=max(w,a[i]);
    }
    scanf("%lld",&m);
    if(m==1)
    {
        printf("%lld\n",w);
    }
    else
    {

        l=1;r=w;
        while(l<r)
        {
            t=0;
            long long mid=(l+r)/2;
           for(int i=1;i<=n;i++)
           {
               if(a[i]>mid)
               {
                   t+=ceil((a[i]-mid)*1.0/(m-1));
               }

           }
           if(t>mid)
           {
              l=mid+1;

           }
           else if(t<=mid)
           {
               r=mid;
           }

        }
        printf("%lld\n",r);
    }
    return 0;
}