-
Notifications
You must be signed in to change notification settings - Fork 0
/
03-05
75 lines (63 loc) · 1.65 KB
/
03-05
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
66
67
68
69
70
71
72
73
74
75
//User function template for C++
class Solution
{
public:
long long int getMax(int arr[], int n)
{
int max = INT_MIN;
for (int i = 0; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
// return the sum of the elements in the array
long long int getSum(int arr[], int n)
{
long long int total = 0;
for (int i = 0; i < n; i++)
total += arr[i];
return total;
}
// find minimum required painters for given maxlen
// which is the maximum length a painter can paint
long long int numberOfPainters(int arr[], int n, int maxLen)
{
long long int total = 0, numPainters = 1;
for (int i = 0; i < n; i++) {
total += arr[i];
if (total > maxLen) {
// for next count
total = arr[i];
numPainters++;
}
}
return numPainters;
}
int partition(int arr[], int n, int k)
{
long long int lo = getMax(arr, n);
long long int hi = getSum(arr, n);
while (lo < hi) {
long long int mid = lo + (hi - lo) / 2;
long long int requiredPainters = numberOfPainters(arr, n, mid);
// find better optimum in lower half
// here mid is included because we
// may not get anything better
if (requiredPainters <= k)
hi = mid;
// find better optimum in upper half
// here mid is excluded because it gives
// required Painters > k, which is invalid
else
lo = mid + 1;
}
// required
return lo;
}
long long minTime(int arr[], int n, int k)
{
return partition(arr,n,k);
// code here
// return minimum time
}
};