E:二分+數學計算

題意：

最讓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

#include<bits/stdc++.h>  
                using namespace std;        

#define maxn 100100  
                #define ll long long int n; 
                  ll a[maxn],k; bool C(ll mid)//計算使用吹風機的時間 
                  {
                         ll sum=0;
                         for(int i=0;i<n;i++){
                             if(a[i]>mid){
                                 sum+=(a[i]-mid)/k;
                                 if((a[i]-mid)%k)//取整的做法，因為存在小數
                                     sum++;
                                 if(sum>mid)
                                     return false;
                             }
                         }
                         return true; } 
                         int main() {
                         while(scanf("%d",&n)!=EOF)
                         {
                             ll big=0,ans;
                             for(int i=0;i<n;i++){
                                 scanf("%lld",&a[i]);
                                 big=big>a[i]?big:a[i];
                             }
                             scanf("%lld",&k);
                             if(k==1){
                                 printf("%lld\n",big);
                                 continue;
                             }
                             ll left=1,right=big;
                             ll mid;
                             k--;
                             while(left<=right)
                             {
                                 mid=(right-left)/2+left;
                                 if(C(mid))
                                     right=mid-1,ans=mid;
                                 else
                                     left=mid+1;
                             }
                             printf("%lld\n",ans);
                         }
                         return 0; }