aboutsummaryrefslogtreecommitdiff
path: root/eliminate_max_monster.c
diff options
context:
space:
mode:
Diffstat (limited to 'eliminate_max_monster.c')
-rw-r--r--eliminate_max_monster.c53
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
+}