题目大意:你有一台机器可以烘干衣物,现在有n个衣物需要烘干,每件衣服都有一个值表示含水量,烘干机一秒可以烘干k滴水,一件衣服不在烘干机上时会每秒自动蒸发一滴水,求最少用多少时间烘干所有衣服。
分析:
二分总时间,我们知道,如果一件衣服的含水量不超过总时间,就没有必要用烘干机烘干。对于超过的衣服,我们设它在烘干机上烘的时间为x,自己蒸发的时间为mid-x(mid为二分的时间),如果能烘干衣服,则可得到关系k*x+mid-x>=a[i],得到x>=(a[i]-mid)/(k-1),因为我们希望在能蒸干这件衣服前提下让在烘干机上的时间最短,这样才能使别的衣物有更多时间,所已x取最小值(注意向上取整),我们把所有衣物在烘干机上的最短时间加起来,判断有没有超过mid,然后改变上下界,最终找到答案。
代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
![](https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)
program drying;var a:array[0..100000]of int64; n,i,m:longint; k,l,r,v,s,mid,ans:int64;begin assign(input,'drying.in');reset(input);assign(output,'drying.out');rewrite(output); readln(n); for i:=1 to n do begin read(a[i]); r:=r+a[i]; if a[i]>m then m:=a[i];end; readln(k);k:=k-1; if k=0 then writeln(m) else begin l:=1; while l<=r do begin mid:=(l+r) div 2;s:=0; for i:=1 to n do if a[i]>mid then s:=s+ord((a[i]-mid) mod k>0)+(a[i]-mid) div k; if s<=mid then begin ans:=mid; r:=mid-1; end else l:=mid+1; end; writeln(ans); end; close(input); close(output);end.