POJ-3104 Drying---二分答案判断是否可行

题目链接：

https://cn.vjudge.net/problem/POJ-3104

题目大意：

有一些衣服，每件衣服有一定水量，有一个烘干机，每次可以烘一件衣服，每分钟可以烘掉k滴水。每件衣服每分钟可以自动蒸发掉一滴水，用烘干机烘衣服时不蒸发。问最少需要多少时间能烘干所有的衣服。

解题思路：

二分答案，然后判断是否可行，如果可行说明当前解>=最优解，区间左移（r = mid - 1）

反之区间右移

坑点：k = 1的时候需要特判。

而且在特判一个解得时候，对每件衣服的水量先减去所花的时间，此时计算烘干机的时间的时候，蒸发量是k - 1而不是k，因为每分钟蒸发一滴水已经算过了

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e6 + ;

 int n, k;

 const ll INF = 1e9 + ;

 ll a[maxn];

 bool judge(ll x)

 {

     ll sum = ;

     for(int i = ; i <= n; i++)

     {

         if(a[i] - x > 0LL)

         {

             sum += (a[i] - x + k - ) / (k - );//使用烘干机的时间

         }

     }

     return sum <= x;

 }

 int main()

 {

     cin >> n;

     for(int i = ; i <= n; i++)scanf("%lld", &a[i]);

     cin >> k;

     if(k == )

     {

         cout<<(*max_element(a + , a +  + n))<<endl;

         return ;

     }

     ll l = , r = INF, ans;

     while(l <= r)

     {

         ll mid = (l + r) / ;

         if(judge(mid))

         {

             ans = mid;

             r = mid - ;

         }

         else l = mid + ;

     }

     cout<<ans<<endl;

     return ;

 }