poj3104 Drying

Posted on | In |

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

要知道如果想要晾干衣服的话，最好的方法就是使用机器冲干x1秒，然后等待风干x2秒。我们来二分答案mid，表示能在mid秒钟晒干。
机器烘干需要x1秒钟，自然烘干需要mid-x1秒钟，得到如下公式x1*k+(mid-x1) >= a[i]所以：x >= (a[i] – mid) / (k – 1)。

当k==1的时候,除数为0 单独讨论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//二分一个答案，然后判断可行性
//知道如果想要晾干衣服的话，最好的方法就是使用机器冲干x1秒，然后等待风干x2秒。我们来二分答案mid，表示能在mid秒钟晒干。

#include<iostream>
#include<cmath>
#include<algorithm>
int n,a[10000],k;
using namespace std;
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	scanf("%d",&a[i]);
	scanf("%d",&k);
	sort(a,a+n);
	int maxValue=a[n-1];
	int ans=0,L,R;
	L=1;
	R=maxValue;
	if(k==1) cout<<maxValue<<endl;
	else{

	while(L<=R){
		int mid=(L+R)/2;
		int sum=0;
		for(int i=0;i<n;i++){
			if(a[i]>mid){
				int x=ceil((a[i]-mid)*1.0/(k-1));
				sum+=x;
			}
			
		}
		if(sum<=mid)//能完成晒干 
		 {
			ans=mid;
			R=mid-1;
		}

		else L=mid+1;
		
	}
	cout<<ans<<endl;
		}
	
	
	return 0;
}

补充

double ceil (double x);

ceil返回不小于value 的下一个整数，value 如果有小数部分则进一位。ceil() 返回的类型仍然是float，因为float 值的范围通常比integer 要小。