// 2106. Maximum Fruits Harvested After at Most K Steps #include "leetcode.h" /* * fruits are available at some positions on an infinite x-axis. you are given a * 2d integer array 'fruits' where 'fruits[i] = [positions[i], amount[i]]' * depicts 'amount[i]' fruits at the position 'position[i]'. 'fruits' is already * sorted by 'position[i]' in ascending order, and eash 'position[i]' is unique. * you are also given an integer 'startPos' and an integer 'k'. initially, y-u * are at the position 'startPos'. from any position, you can either walk to the * left or right. it takes one step to move one unit on the x-axis, and you can * walk at most 'k' steps in total. for every position you reach, you harvest * all the fruits at that position, and the fruits will dsiappear from that * position. */ void bfs(int **fruits, int fruitsSize, int start, int *left, int *right) { *left = 0; *right = fruitsSize - 1; while (*left <= *right) { int mid = (*left + *right) / 2; if (fruits[mid][0] < start) *left = mid + 1; else if (fruits[mid][0] > start) *right = mid - 1; else { *left = mid; *right = mid; break; } } } int find_max_right(int **fruits, int fruitsSize, int curr, int k) { int startPos = curr, max_left = curr - 1, sum_left = 0, max = 0, sum_right = 0; for (; max_left >= 0; max_left--) { if ((fruits[curr][0] - fruits[max_left][0]) < k) sum_left += fruits[max_left][1]; else { max_left++; break; } } if (max_left == -1) max_left++; while (1) { sum_right += fruits[curr][1]; if (sum_right + sum_left > max) max = sum_right + sum_left; if (curr == fruitsSize - 1) break; else { curr++; k -= fruits[curr][0] - fruits[curr - 1][0]; if (k < 0) break; else if (k > fruits[curr][0] - fruits[startPos][0]) { while (max_left < startPos && fruits[curr][0] - fruits[max_left][0] > k) { sum_left -= fruits[max_left][1]; max_left++; } } else sum_left = 0; } } return max; } int find_max_left(int **fruits, int fruitsSize, int curr, int k) { int startPos = curr, max_right = curr + 1, sum_right = 0, max = 0, sum_left = 0; for (; max_right < fruitsSize; max_right++) { if (fruits[max_right][0] - fruits[curr][0] <= k) sum_right += fruits[max_right][1]; else { max_right--; break; } } if (max_right == fruitsSize) max_right--; while (1) { sum_left += fruits[curr][1]; if (sum_right + sum_left > max) max = sum_right + sum_left; if (!curr) break; else { curr--; k -= fruits[curr + 1][0] - fruits[curr][0]; if (k < 0) break; else if (k > fruits[startPos][0] - fruits[curr][0]) { while (max_right > startPos && fruits[max_right][0] - fruits[curr][0] > k) { sum_right -= fruits[max_right][1]; max_right--; } } else sum_right = 0; } } return max; } int maxTotalFruits(int **fruits, int fruitsSize, int *fruitsColSize, int startPos, int k) { int left = -1, right = -1; bfs(fruits, fruitsSize, startPos, &right, &left); if (right < fruitsSize) { int new_k = k - (fruits[right][0] - startPos); right = new_k >= 0 ? find_max_right(fruits, fruitsSize, right, new_k) : 0; } else right = 0; if (left > -1) { int new_k = k - (startPos - fruits[left][0]); left = new_k >= 0 ? find_max_left(fruits, fruitsSize, left, new_k) : 0; } else left = 0; return left > right ? left : right; } int main() { int f1[3][2] = {{2, 8}, {6, 3}, {8, 6}}, f2[6][2] = {{0, 9}, {4, 1}, {5, 7}, {6, 2}, {7, 4}, {10, 9}}, f3[3][2] = {{0, 3}, {6, 4}, {8, 5}}; int fcs1 = ARRAY_SIZE(f1), fcs2 = ARRAY_SIZE(f2), fcs3 = ARRAY_SIZE(f3); printf("%d\n", maxTotalFruits((int **)f1, ARRAY_SIZE(f1[0]), &fcs1, 5, 4)); // expect: 9 printf("%d\n", maxTotalFruits((int **)f2, ARRAY_SIZE(f2[0]), &fcs2, 5, 4)); // expect: 14 printf("%d\n", maxTotalFruits((int **)f3, ARRAY_SIZE(f3[0]), &fcs3, 3, 2)); // expect: 0 }