傳送門：

Drying

題意：

有一堆衣服需要乾燥，烘衣機每分鐘可以降低濕度值Ｋ，不烘的話每分鐘只能降低濕度值１。
注意如果使用烘衣機每分鐘不是降低K+1！
求所有衣服乾燥完畢所需的最少時間。

思路：

二分搜答案即可, 判定時假設使用ｂ分鐘乾燥此衣服，則最少需要幾分鐘的烘衣機，若全部衣服需要使用的烘乾時間＞ｂ則失敗。

每件衣服晾ａ分鐘、烘（ｂ−ａ）分鐘，濕度值Ｘ：

\( a +\left( b-a \right)\cdot K\; \geq \; X \)
\( a\cdot \left( 1-K \right)\;\;\;\;\;\; \geq \; X-bK \)
\( a\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \leq \; \frac{X-bK}{1-K} \)
\( -a\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \geq \; \frac{X-bK}{K-1} \)
\( b-a\;\;\;\;\;\;\;\;\;\;\;\; \geq \; \frac{bK-b+X-bK}{K-1}\;\;\; =\;\;\; \frac{X-b}{K-1} \)

經過上面簡單推導，可以得知在二分搜的判定function內，每件衣服所需的烘衣機時間為 ceil(\( \frac{X-b}{K-1} \))。
注意K=1時需例外處理。

X為每件衣服的濕度值、b為二分搜的總花費時間、K為烘衣機每分鐘降低的濕度值，總烘衣時間若大於b則失敗。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void init(){
  N = getint();
  for(int i=0;i<N;i++){
    arr[i] = getint();
    R = max(R, arr[i]);
  }
  M = getint();
  ++R;
  sort(arr, arr+N);
}
inline bool suc(const ll &x){
  int flag = 0;
  cnt = 0;
  while(flag<N && arr[flag]<=x)
    ++flag;
  for(;flag<N;flag++)
    cnt += ((arr[flag]-x)/(M-1) + (((arr[flag]-x)%(M-1))>0));
  return cnt <= x;
}

ll sol(){
  if(M == 1)
    return R-1;
#define mid ((L+R)>>1)
  while(R-L>1)                // (]
    suc(mid) ? R=mid : L=mid;
  return R;
}

int main(){
  init();
  cout << sol() << endl;
}