diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /min_cost_ticket.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'min_cost_ticket.c')
-rw-r--r-- | min_cost_ticket.c | 54 |
1 files changed, 54 insertions, 0 deletions
diff --git a/min_cost_ticket.c b/min_cost_ticket.c new file mode 100644 index 0000000..88abdb2 --- /dev/null +++ b/min_cost_ticket.c @@ -0,0 +1,54 @@ +// 983. Minimum Cost For Tickets +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> + +/* + * you have planned some train traveling one year in advance. the days of the + * year in which you will travel are given as an integer array 'days'. each day + * is an integer 1 - 365. train tickets are sold in three different ways: 1 day + * pass sold for 'costs[0]' dollars 7 day pass sold for 'costs[1]' dollars 30 + * day pass sold for 'costs[2]' dollars the passes allow that many days of + * consecutive travel. return mininum number of dollars you need to travel every + * day in the given list of days. + */ + +#define MIN(a, b, c) \ + ((a) < (b) ? ((a) < (c) ? (a) : (c)) : ((b) < (c) ? (b) : (c))) + +bool find_item(int *days, int days_size, int target) { + int left = 0, right = days_size - 1, mid; + while (left <= right) { + mid = (left + right) / 2; + if (days[mid] == target) + return true; + if (days[mid] > target) + right = mid - 1; + else + left = mid + 1; + } + return false; +} + +int mincostTickets(int *days, int days_size, int *costs, int costs_size) { + int arr_size = days[days_size - 1] + 30; + int *dp = calloc(arr_size, sizeof(int)); + for (int i = 30; i < arr_size; i++) { + if (find_item(days, days_size, i - 29) == false) + dp[i] = dp[i - 1]; + else + dp[i] = MIN(dp[i - 1] + costs[0], dp[i - 7] + costs[i], + dp[i - 30] + costs[2]); + } + int ans = dp[arr_size - 1]; + free(dp); + return ans; +} + +int main() { + int d1[] = {1, 4, 6, 7, 8, 20}, + d2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31}; + int c1[] = {2, 7, 15}; + printf("%d\n", mincostTickets(d1, 6, c1, 3)); // expect: 11 + printf("%d\n", mincostTickets(d2, 12, c1, 3)); // expect: 11 +} |