aboutsummaryrefslogtreecommitdiff
path: root/max_num_robot_budget.c
blob: 7b1dbb2198b53a563b45961e8ce620c77ba693de (plain)
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
}