POJ 3104 Drying 二分

来源：http://poj.org/problem?id=3104

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

思路：首先可以想到二分枚举答案。枚举一个mid值时，若一件衣服的水量大于mid，则一件衣服的最短时间是烘干一段时间，在自己蒸发一段时间。可以算出烘干的时间，为(num[i] - mid) / (k - 1)。这样把所有衣服的时间加起来，判断可行即可。

代码：

#include <iostream>#include <cstdio>#include <cmath>#include <string.h>using namespace std;const int N = 100010;typedef long long LL;LL num[N];int main(){//freopen("1.txt","r",stdin);int n;while(scanf("%d",&n) != EOF){LL maxvalue = 0,rp = 0;memset(num,0,sizeof(num));for(int i = 0; i < n; ++i){   scanf("%lld",&num[i]);   if(num[i] > maxvalue)   maxvalue = num[i];}LL k;scanf("%lld",&k);if(k == 1){  printf("%lld\n",maxvalue);  continue;}LL lp = 1,ans = 0;rp = maxvalue;while(lp <= rp){   LL mid = (lp + rp) / 2, sum  = 0;   for(int i = 0; i < n; ++i){   if(num[i] > mid){     long long xx = ceil((num[i] - mid ) * 1.0 / (k - 1) ); sum += xx;   }   }   if(sum <= mid){     ans = mid; rp = mid - 1;   }   else   lp = mid + 1;}printf("%lld\n",ans);}return 0;}