diff options
author | Jack Sangdahl <[email protected]> | 2024-10-30 22:15:54 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-30 22:15:54 -0600 |
commit | 45a8af12d6d2f60e1efdba06d853aaff9055193f (patch) | |
tree | 635420d1abe138bb45c2b73f49d4df8b26782c59 /min_total_distance_traveled.c | |
parent | 80c009131135eef4b5c611a9d8091abdf94a8f30 (diff) | |
download | leetcode-45a8af12d6d2f60e1efdba06d853aaff9055193f.tar.gz leetcode-45a8af12d6d2f60e1efdba06d853aaff9055193f.zip |
2463. minimum total distance traveled
Diffstat (limited to 'min_total_distance_traveled.c')
-rw-r--r-- | min_total_distance_traveled.c | 245 |
1 files changed, 245 insertions, 0 deletions
diff --git a/min_total_distance_traveled.c b/min_total_distance_traveled.c new file mode 100644 index 0000000..b41c3be --- /dev/null +++ b/min_total_distance_traveled.c @@ -0,0 +1,245 @@ +// 2463. Minimum Total Distance Traveled +#include "leetcode.h" + +/* + * there are some robots and factories on the x-axis. you are given an integer + * array 'robot' where 'robot[i]' is the position of the i'th robot. you are + * also given a 2d integer array 'factory' where 'factory[j] = [position_i, + * limit_i]' indicates that 'position[j]' is the position of the j'th factory + * and that the j'th factory can repair at most 'limit[j]' robots. the positions + * of each robot are unique. note that a robot can be in the same position as a + * factory initially. all the robots are initially broke; they keep moving in + * one direction. the direction could be the negative or positive direction of + * the x-axis. when a robot reaches a factory that did not reach its limit, the + * factory repairs the robot and it stops moving. return the minimum total + * distance traveled by all the robots. the test cases are generated as such + * that all the robots can be repaired. + */ + +struct robot { + bool to_left; + int right; + int left; +}; + +struct factory { + int *robot_num; + int point; + int count; +}; + +int cmp_r(const void *a, const void *b) { + return *(int *)a > *(int *)b ? 1 : -1; +} + +int cmp_f(const void **a, const void **b) { + return (*(int **)a)[0] > (*(int **)b)[0] ? 1 : -1; +} + +int cost_r(int **factory, int factorySize, struct factory *f_list, + int right_factory) { + int right = 0; + if (right_factory == factorySize) + return INT_MAX; + while (factory[right_factory][1] <= f_list[right_factory].count) { + right += factory[right_factory][0] - factory[right_factory - 1][0]; + right_factory++; + if (right_factory == factorySize) + return INT_MAX; + } + right += factory[right_factory][0] - factory[right_factory - 1][0]; + return right; +} + +void cost_f(int *robot, int **factory, struct robot *r_list, + struct factory *f_list, int curr, int left_factory, bool *to_left, + int *l, int r) { + if (left_factory == -1) { + r_list[curr].left = -1; + return; + } + *l += robot[curr] - factory[left_factory][0]; + if (factory[left_factory][1] <= f_list[left_factory].count) { + int replace = f_list[left_factory].robot_num[f_list[left_factory].point]; + *l -= r_list[replace].to_left ? robot[replace] - factory[left_factory][0] + : factory[left_factory][0] - robot[replace]; + cost_f(robot, factory, r_list, f_list, replace, r_list[replace].left, + to_left, l, r); + if (*to_left) + f_list[left_factory].point++; + } else { + if (*l <= r) + *to_left = true; + } + if (*to_left) { + r_list[curr].to_left = true; + r_list[curr].left = left_factory - 1; + f_list[left_factory].robot_num[f_list[left_factory].count] = curr; + f_list[left_factory].count++; + } + return; +} + +void to_r_change(int **factory, struct robot *r_list, struct factory *f_list, + int curr, int right_factory) { + if (factory[right_factory][1] <= f_list[right_factory].count) { + int replace = f_list[right_factory].robot_num[f_list[right_factory].point]; + to_r_change(factory, r_list, f_list, replace, r_list[replace].left); + f_list[right_factory].point++; + } + r_list[curr].right = right_factory + 1; + f_list[right_factory].robot_num[f_list[right_factory].count] = curr; + f_list[right_factory].count++; + return; +} + +long long minimumTotalDistance(int *robot, int robotSize, int **factory, + int factorySize, int *factoryColSize) { + qsort(robot, robotSize, sizeof(int), cmp_r); + qsort(factory, factorySize, sizeof(int *), cmp_f); + struct robot *r_list = + (struct robot *)malloc(robotSize * sizeof(struct robot)); + struct factory *f_list = + (struct factory *)calloc(factorySize, sizeof(struct factory)); + int point = 0, head = 0; + long long ans = 0; + for (int i = 0; i < robotSize; i++) { + while (point < factorySize && factory[point][0] < robot[i]) + point++; + r_list[i].right = point; + r_list[i].left = point - 1; + } + for (int i = 0; i < factorySize; i++) + f_list[i].robot_num = (int *)malloc(robotSize * sizeof(int)); + while (head < robotSize && r_list[head].left == -1) { + while (factory[r_list[head].right][1] == f_list[r_list[head].right].count) + r_list[head].right++; + ans += factory[r_list[head].right][0] - robot[head]; + r_list[head].to_left = false; + f_list[r_list[head].right].robot_num[f_list[r_list[head].right].count] = + head; + f_list[r_list[head].right].count++; + head++; + } + while (head < robotSize) { + int left = r_list[head].left == -1 + ? INT_MAX + : robot[head] - factory[r_list[head].left][0]; + int right = r_list[head].right == factorySize + ? INT_MAX + : factory[r_list[head].right][0] - robot[head]; + int right_factory = r_list[head].right; + bool to_left = false; + if (right_factory < factorySize) { + while (!factory[right_factory][1]) { + right_factory++; + if (right_factory == factorySize) { + right = INT_MAX; + break; + } else + right = factory[right_factory][0] - robot[head]; + } + if (right_factory < factorySize && + factory[right_factory][1] <= f_list[right_factory].count) { + r_list[head].to_left = false; + ans += right; + f_list[right_factory].robot_num[f_list[right_factory].count] = head; + f_list[right_factory].count++; + int replace = + f_list[right_factory].robot_num[f_list[right_factory].point]; + f_list[right_factory].point++; + if (r_list[replace].left == -1) { + r_list[head].left = -1; + right_factory++; + ans += factory[right_factory][0] - factory[right_factory - 1][0]; + while (factory[right_factory][1] <= f_list[right_factory].count) { + f_list[right_factory].robot_num[f_list[right_factory].count] = + replace; + replace = + f_list[right_factory].robot_num[f_list[right_factory].point]; + f_list[right_factory].count++; + f_list[right_factory].point++; + right_factory++; + ans += factory[right_factory][0] - factory[right_factory - 1][0]; + } + f_list[right_factory].robot_num[f_list[right_factory].count] = + replace; + f_list[right_factory].count++; + f_list[right_factory].point++; + } else { + right = cost_r(factory, factorySize, f_list, right_factory + 1); + left = robot[replace] - factory[right_factory][0]; + cost_f(robot, factory, r_list, f_list, replace, r_list[replace].left, + &to_left, &left, right); + if (to_left) + ans += left; + else { + ans += right; + to_r_change(factory, r_list, f_list, replace, + r_list[replace].right); + } + } + head++; + continue; + } + } + int left_factory = r_list[head].left; + while (!factory[left_factory][1]) { + left_factory--; + if (left_factory >= 0) { + left = robot[head] - factory[left_factory][0]; + r_list[head].left = left_factory; + } else { + left = INT_MAX; + r_list[head].left = left_factory; + break; + } + } + if (left_factory >= 0 && + factory[left_factory][1] <= f_list[left_factory].count) { + int replace = f_list[left_factory].robot_num[f_list[left_factory].point]; + left -= r_list[replace].to_left + ? robot[replace] - factory[left_factory][0] + : factory[left_factory][0] - robot[replace]; + cost_f(robot, factory, r_list, f_list, replace, r_list[replace].left, + &to_left, &left, right); + if (to_left) + f_list[left_factory].point++; + } else { + if (left <= right) + to_left = true; + } + if (to_left) { + ans += left; + r_list[head].to_left = true; + r_list[head].left = left_factory - 1; + f_list[left_factory].robot_num[f_list[left_factory].count] = head; + f_list[left_factory].count++; + } else { + ans += right; + r_list[head].to_left = false; + f_list[right_factory].robot_num[f_list[right_factory].count] = head; + f_list[right_factory].count++; + } + head++; + } + for (int i = 0; i < factorySize; i++) + free(f_list[i].robot_num); + free(f_list), free(r_list); + return ans; +} + +int main() { + int r1[] = {0, 4, 6}, f1i[2][2] = {{2, 2}, {6, 2}}; + int r2[] = {1, -1}, f2i[2][2] = {{-2, 1}, {2, 1}}; + struct two_d_arr f1, f2; + two_d_arr_init(&f1, 2, 2, f1i); + two_d_arr_init(&f2, 2, 2, f2i); + printf("%lld\n", minimumTotalDistance(r1, ARRAY_SIZE(r1), f1.arr, f1.row_size, + f1.col_size)); // expect: 4 + + printf("%lld\n", minimumTotalDistance(r2, ARRAY_SIZE(r2), f2.arr, f2.row_size, + f2.col_size)); // expect: 2 + two_d_arr_free(&f1); + two_d_arr_free(&f2); +} |