贪心算法——烘干衣服问题_烘干衣物算法题

现有n件衣服需要烘干，每件衣服的含水量为ai，如果自然晾干，每分钟含水量减少1；如果使用烘干机烘干，每分钟含水量减少k（直至为0）。只有一台烘干机，每次只能烘干一件衣服，且一次至少使用1分钟。求使所有衣服含水量为0的最少时间是多少。

#include<stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;

const int MAXN = 1e5+10;
int water[MAXN];

//判断在时间time内是否可以将所有衣服烘干 
bool judge(int n,int k,int time){
	int sum = 0;
	for(int i = 0;i < n; ++i){
		if(water[i] > time){
			sum += ceil((water[i] - time)*1.0 / (k-1));
		} 
		if(sum > time)
			return false;
	}
	return true;
}

int main()
{
	int n;
	scanf("%d",&n);
	for(int i = 0;i < n; ++i){
		scanf("%d",&water[i]);
	} 
	int k;
	scanf("%d",&k);
	sort(water,water+n);
	if(k == 1)
		printf("%d\n",water[n-1]);
	else{
		//二分法找满足条件的最小值 
		int left = 1;
		int right = water[n-1];
		while(left <= right){
			int middle = left + (right - left)/2;
			if(judge(n,k,middle)){
				right = middle - 1;
			}
			else{
				left = middle + 1;
			}
		} 
		printf("%d",left);
		
	}
	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