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
}
|