poj3104（二分）
题目链接：http://poj.org/problem?id=3104
题意：有n件衣服，每一件含有a[i]单位的水，每分钟衣服可以自然蒸发1单位的水，也可以在烘干器上每分钟烘干k单位的水，问将所有衣服烘干的最短用时。
思路：最短用时最小为1，最大为Max（a[i]中的最大值），即k=1的情况。所以可以利用二分不断逼近答案，并判断。若m符合，则在[l,m-1]里查找，否则在[m+1,r]里查找。判断处：显然a[i]小于m的衣服不用烘干机，可以自己蒸发干，对于大于m的衣服假设需要烘干机x分钟，则(m-x)+k*x>=a[i]，得x=ceil((a[i]-m)*1.0/(k-1))故对于k=1的情况需要特判。详见代码：
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 6 int n,k,Max,res; 7 int a[100005]; 8 9 bool check(int p){ 10 long long sum=0; 11 for(int i=0;i<n;++i) 12 if(a[i]>p) sum+=ceil((a[i]-p)*1.0/(k-1)); 13 return sum<=p; 14 } 15 16 int main(){ 17 scanf("%d",&n); 18 for(int i=0;i<n;++i){ 19 scanf("%d",&a[i]); 20 if(a[i]>Max) Max=a[i]; 21 } 22 scanf("%d",&k); 23 if(k==1){ 24 printf("%d ",Max); 25 return 0; 26 } 27 int l=1,r=Max,m; 28 while(l<=r){ 29 m=(l+r)>>1; 30 if(check(m)) 31 res=m,r=m-1; 32 else 33 l=m+1; 34 } 35 printf("%d ",res); 36 return 0; 37 }