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
|
// 2398. Maximum Number of Robots Within Budget
#include "leetcode.h"
/*
* you have 'n' robots. you are given two 0 indexed integer arrays 'chargeTimes'
* and 'runningCosts', both of length 'n'. the i'th robot costs 'chargeTimes[i]'
* units to charge and costs 'runningCosts[i]' units to run. you are also given
* an integer 'budget'. the total cost of running 'k' chosen robots is equal to
* 'max(chargeTimes) + k * sum(runningCosts)' where 'max(chargeTimes)' is the
* largest charge cost among the 'k' robots and 'sum(runningCosts)' is the sum
* of running costs among the 'k' robots. return the maximum number of
* consecutive robots you can run such that the total costs does not exceed
* 'budget'.
*/
int maximumRobots(int *chargeTimes, int chargeTimesSize, int *runningCosts,
int runningCostsSize, long long budget) {
int lut[50001], idx_head = 0, idx_tail = 0, ans = 0, curr_len = 0;
long long curr_cost = 0;
for (int i = 0; i < chargeTimesSize; i++) {
long long curr_sum;
curr_cost += runningCosts[i];
while (idx_head < idx_tail && lut[idx_head] < i - curr_len)
idx_head++;
while (idx_head < idx_tail &&
chargeTimes[lut[idx_tail - 1]] < chargeTimes[i])
idx_tail--;
lut[idx_tail++] = i;
curr_sum = chargeTimes[lut[idx_head]];
curr_sum += (long long)(++curr_len * curr_cost);
while (curr_len > 0 && curr_sum > budget) {
curr_cost -= runningCosts[i - (--curr_len)];
while (idx_head < idx_tail && lut[idx_head] < i - curr_len)
idx_head++;
curr_sum = chargeTimes[lut[idx_head]];
curr_sum += (long long)(curr_len * curr_cost);
}
if (ans < curr_len)
ans = curr_len;
}
return ans;
}
int main() {
int ct1[] = {3, 6, 1, 3, 4}, ct2[] = {11, 12, 19}, rc1[] = {2, 1, 3, 4, 5},
rc2[] = {10, 8, 7};
printf("%d\n", maximumRobots(ct1, ARRAY_SIZE(ct1), rc1, ARRAY_SIZE(rc1),
25)); // expect: 3
printf("%d\n", maximumRobots(ct2, ARRAY_SIZE(ct2), rc2, ARRAY_SIZE(rc2),
19)); // expect: 0
}
|