POJ 3104 Drying (经典)【二分答案】

题目大意：

有一些衣服，每件衣服有一定水量，有一个烘干机，每次可以烘一件衣服，每分钟可以烘掉k滴水。每件衣服没分钟可以自动蒸发掉一滴水，用烘干机烘衣服时不蒸发。问最少需要多少时间能烘干所有的衣服。

解题分析：

本题用二分答案求解，解题思路就是二分时间，再对每个物品依据当前二分的时间进行判断，如果该物品水量小于等于总时间，那么就等其自然风干即可，如果大于总时间，那么要使当前枚举的答案成立，该衣服必然要消耗一定的机器清洗时间，算出所有衣服需要消耗的时间，将其与枚举的答案比较，即可判断答案的正确性。

假设当前枚举的总共清洗时间为mid,衣服水量为a[i],需要机洗x分钟,那么必然需要满足等式 x*k+mid-x>=a[i] ,整理之后可得：x>=(a[i]-mid)/(k-1)，因为x依据题意只能取整数，所以我们需要用到ceil()函数来向上取整，得到符合条件的最小x值，注意，由于除数不能为0，所以k==1是需要特判一下。

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 typedef long long ll;
 7 const int M =1e5+10;
 8 int n;
 9 ll arr[M],maxval,k;
10 
11 bool check(ll m){
12     ll res=0;
13     for(int i=1;i<=n;i++){
14         if(arr[i]>m)
15             res+=ceil((arr[i]-m)*1.0/(k-1)*1.0);     //得到该物品在这种时间限制下至少要用机器洗的次数 
16     }
17     if(res<=m)return true;
18     return false;
19 }
20 ll binary_ans(){
21     ll l=1,r=maxval;
22     ll ans=-1;
23     while(l<=r){
24         ll mid=(l+r)>>1;
25         if(check(mid))ans=mid,r=mid-1;
26         else l=mid+1;
27     }
28     return ans;
29 }
30 int main(){
31     while(scanf("%d",&n)!=EOF){
32         maxval=-M;
33         for(int i=1;i<=n;i++){
34             scanf("%lld",&arr[i]);
35             maxval=max(maxval,arr[i]);
36         }
37         scanf("%lld",&k);
38         if(k==1)printf("%lld
",maxval);     //k==1需要特判，因为除数不能为0 
39         else printf("%lld
",binary_ans());
40     }
41 }

2018-09-20