POJ.3104 Drying

1.Problem
http://poj.org/problem?id=3104

2.Idea
Binary Search

3.Source

 ll N, K;  
 ll a[100005];  
 ll MaxL = 0;  
 bool C(ll d)  
 {  
      ll cnt = 0;  
      for (int i = 0; i < N; i++) {  
           if (a[i] > d) {  
                cnt += ceil((a[i] - d) * 1.0 / (K - 1));  
           }  
      }  
      return cnt <= d;  
 }  
 void solve()  
 {  
      if (K == 1) {  
           printf("%d\n", MaxL);  
           return;  
      }  
      ll lb = 0, ub = MaxL;  
      while (ub - lb > 1) {  
           //cout << lb << " " << ub << endl;  
           ll mid = (lb + ub) / 2;  
           if (C(mid)) ub = mid;  
           else lb = mid;  
      }  
      printf("%d\n", ub);  
 }  
 int main()  
 {  
      cin >> N;  
      for (int i = 0; i < N; i++) {   
           scanf("%d", &a[i]);  
           MaxL = max(MaxL, a[i]);  
      }  
      cin >> K;  
      solve();  
      return 0;  
 }