diff options
Diffstat (limited to 'eliminate_max_monster.c')
-rw-r--r-- | eliminate_max_monster.c | 53 |
1 files changed, 53 insertions, 0 deletions
diff --git a/eliminate_max_monster.c b/eliminate_max_monster.c new file mode 100644 index 0000000..f43bfbe --- /dev/null +++ b/eliminate_max_monster.c @@ -0,0 +1,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 +} |