poj 3104Drying解题报告

二分答案，对于进行枚举的答案，如果自然风干的时间比其要短，那就让它自然风干，否则就保证一个物体占用甩干机的时间最短，即为(time[i]-t)/(k-1)

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define N 100005
 5 using namespace std;
 6 int time[N];
 7 int n,k;
 8 bool check(int t)
 9 {
10     int i;
11     int cnt=0;
12     for(i=0;i<n;i++)
13     {
14         if(time[i]<=t)
15         continue;
16         double temp=(double)(time[i]-t)/(k-1);
17         cnt+=(int)temp;
18         if(temp-(int)temp>0)
19         ++cnt;
20         if(cnt>t)
21         return false;
22     }
23     return cnt<=t;
24 }
25 int main()
26 {
27     int low,high,mid,ans,i;
28     while(scanf("%d",&n)!=EOF)
29     {
30         high=0;
31         low=0;
32         for(i=0;i<n;i++)
33         {
34             scanf("%d",&time[i]);
35             if(time[i]>high)
36             high=time[i];
37         }
38         scanf("%d",&k);
39         if(k==1)
40         {
41             printf("%d\n",high);
42             continue;
43         }
44         ans=high;
45         while(low<=high)
46         {
47             mid=low+(high-low)*0.5;
48             if(check(mid))
49             {
50                 ans=mid;
51                 high=mid-1;
52             }
53             else
54             low=mid+1;
55         }
56         printf("%d\n",ans);
57     }
58     return 0;
59 }