【POJ No. 3104】 烘干衣服 Drying

【POJ No. 3104】 烘干衣服 Drying

POJ题目地址

【题意】

可以使用散热器烘干衣服。但散热器很小，所以它一次只能容纳一件衣服。

简有n 件衣服，每件衣服在洗涤过程中都带有ai 的水。在自然风干的情况下，每件衣服的含水量每分钟减少1（只有当物品还没有完全干燥时）。当含水量变为零时，布料变干并准备好包装。

在散热器上烘干时，衣服的含水量每分钟减少k （如果衣服含有少于k 的水，则衣服的含水量变为零）。请有效地使用散热器来最小化烘干的总时间。

【输入输出】

输入：

第1行包含一个整数n （1≤n ≤10^5 ）；第2行包含ai（1≤ai ≤10^9 ，1≤i ≤n ）；第3行包含k （1≤k ≤10^9 ）。

输出：

单行输出烘干所有衣服所需的最少时间。

【样例】

【思路分析】

假设烘干所有衣服所需的最少时间为mid，如果所有衣服的含水量a [i ]都小于mid，则不需要用烘干机，自然风干的时间也不会超过mid。如果有的衣服a [i ]大于mid，则让所有a [i ]大于mid的衣服使用烘干机，让a [i ]不大于mid的衣服自然风干即可。

假设衣服a [i ]>mid，用了t 时间的烘干机，对剩余的时间mid-t选择自然风干，那么a [i ]=k ×t +mid-t ，t =(a [i ]-mid)/(k-1)。只需判断这些a [i ]大于mid的衣服使用烘干机的总时间有没有超过mid，如果超过，则不满足条件。

【算法设计】

① 按照a [i ]从小到大排序。

② 如果k =1，则直接输出a [n -1]，算法结束。

③ 进行二分搜索，l =1，r =a [n -1]，mid=(l +r )>>1，判断最少烘干时间为mid是否可行，如果可行，则r =mid-1，减少时间继续搜索；否则l =mid+1，增加时间继续搜索。当l >r 时停止。

④ 判断最少烘干时间为mid是否可行。对所有a [i ]>mid的衣服使用烘干机，用sum累加使用烘干机的时间，如果sum>mid，则说明不可行，返回0。当所有衣服都处理完毕时，返回1。

【注意】
① 对t 的结果需要向上取整，因为如果有余数，再用一次烘干机无非就是多1个时间，但是如果自然风干，则至少用1个时间。
② 公式中的分母是k -1，因此在k =1时需要单独判断特殊情况，直接输出最大的含水量即可，不然会超时。

【算法实现】

#include
#include
#include
#include

using namespace std;
int n , k;

int a[100010];

int judge(int x){
	
	int sum = 0;
	for(int i = 0 ; i < n ; i++){
		
		if(a[i] > x){
			sum += (a[i] - x + k - 2) / (k - 1); //向上取整 
		}
		if(sum > x){
			return 0;
		}
	}
	
	return 1;
}

void solve(){
	
	int l = 1 , r = a[n - 1] , ans;
	while(l <= r){
		
		int mid = (l + r) >> 1;
		if(judge(mid)){
			
			ans = mid;
			r = mid - 1; //减小 
		}
		else{
			l = mid + 1; //增大 
		}
	}
	cout << ans << endl;
}

int main(){
	
	while(~scanf("%d", &n)){
		
		for(int i = 0 ; i < n ; i++){
			
			scanf("%d" , &a[i]);
		}
		scanf("%d" , &k);
		sort(a , a + n);
		
		if(k == 1){
			
			printf("%d\n" , a[n - 1]);
			continue;
		}
		solve();
	}
	
	return 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65