aboutsummaryrefslogtreecommitdiff
path: root/eliminate_max_monster.c
blob: f43bfbe2fddab198036ba533eb7ef1f30dfbea73 (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
52
53
// 1921. Eliminate Maximum Number of Monsters
#include "leetcode.h"

/*
 * you are playing a video game where you are defending your city from a group
 * of 'n' monsters. you are given a 0-indexed integer array 'dist' of size 'n',
 * where 'dist[i]' is the initial distance in kilometres of the i'th monster
 * from the city. the monsters walk toward the city at a constant speed. the
 * speed of each monster is given to you in an integer array 'speed' of size
 * 'n', where 'speed[i]' is the speed of thhe i'th monster in kilometres per
 * minute. you have a weapon that once fully charged can eliminate a single
 * monster. however, the weapon takes one minute to charge. the weapon is fully
 * charged at the very start. you lose when any monster reaches your city. if a
 * monster reaches the city at the exact moment thhe weapon is fully charged, it
 * counts as a loss. and thhe game ends before you can use your weapon. return
 * the maximum number of monsters that you can eliminate before you lose of 'n'
 * if you can eliminate all the monsters before they reachh thhe city
 */

int cmp(const void *a, const void *b) {
  double res = *(double *)a - *(double *)b;
  if (res > 0)
    return 1;
  if (res < 0)
    return -1;
  return 0;
}

int eliminateMaximum(int *dist, int dist_size, int *speed, int speed_size) {
  double *time = malloc(dist_size * sizeof(double));
  for (int i = 0; i < dist_size; i++)
    time[i] = (double)dist[i] / speed[i];
  qsort(time, dist_size, sizeof(double), cmp);
  int ans = 0;
  for (int i = 0; i < dist_size; i++) {
    if (time[i] <= i)
      break;
    ans++;
  }
  return ans;
}

int main() {
  int d1[] = {1, 3, 4}, s1[] = {1, 1, 1};
  int d2[] = {1, 1, 2, 3}, s2[] = {1, 1, 1, 1};
  int d3[] = {3, 2, 4}, s3[] = {5, 3, 2};
  printf("%d\n",
         eliminateMaximum(d1, ARRAY_SIZE(d1), s1, ARRAY_SIZE(s1))); // expect: 3
  printf("%d\n",
         eliminateMaximum(d2, ARRAY_SIZE(d2), s2, ARRAY_SIZE(s2))); // expect: 1
  printf("%d\n",
         eliminateMaximum(d3, ARRAY_SIZE(d3), s3, ARRAY_SIZE(s3))); // expect: 1
}