2024年华为OD机试真题-Wonderland

华为OD机试真题-Wonderland-2024年OD统一考试（D卷）

题目描述：

Wonderland是小王居住地一家很受欢迎的游乐园。 Wonderland目前有4种售票方式，分别为一日票（1天）、三日票（3天）、周票（7天）和月票（30天）。

每种售票方式的价格将由一个数组给出，每种票据在票面时限内可以无限制的进行游玩。例如，小王在第10日买了一张三日票，小王可以在第10日、第11日和第12日进行无限制的游玩。

小王计划在接下来一年内多次游玩该游乐园。小王计划的游玩日期将由一个数组给出。 现在，请您根据给出的售票价格数组和小王计划游玩日期数组，返回完成游玩计划所需要的最低消费。

输入描述：

输入为2个数组

售票价格数组为costs，costs.length=4,默认顺序为一日票、三日票、周票和月票。

小王计划游玩日期数组为days，1<=days.length<=365,1<=days[i]<=365,默认顺序为升序。

输出描述：

完成游玩计划的最低消费

补充说明：

样例说明：

根据售票价格数组和游玩日期数组给出的信息，发现每次去玩的时候买一张一日票是最省钱的，所以小王会买8张一日票，每张5元，最低花费是40元。

示例1

输入：

5 14 30 100

1 3 15 20 21 200 202 230

输出：

40

说明：

解题思路：

我们可以使用动态规划（DP）来确定在小王指定游玩的日期最低的消费。这种方法考虑了每个具体日期的最优购票策略，并逐步构建出一整年的最低消费计划。

思路

定义状态： 定义 dp[i] 表示直到第 i 天（含）所需的最低消费。

初始化： 由于小王只在特定的日期游玩，如果某天不游玩，那么这一天的消费应与前一天相同（因为不需要额外购票）。因此，初始化 dp[0] = 0，表示在第0天没有消费。

状态转移： 对于每个具体的游玩日期：

考虑买一日票：dp[day] = dp[day-1] + costs[0]

考虑买三日票：dp[day] = min(dp[day], dp[max(day-3, 0)] + costs[1])

考虑买周票：dp[day] = min(dp[day], dp[max(day-7, 0)] + costs[2])

考虑买月票：dp[day] = min(dp[day], dp[max(day-30, 0)] + costs[3])

计算结果： 最后，dp[last_day] 即为整年的最低消费。

完美分割线~~~~~~~~~~~创作不易，请点击关注、收藏

完美分割线~~~~~~~~~~~创作不易，请点击关注、收藏

完美分割线~~~~~~~~~~~创作不易，请点击关注、收藏

完美分割线~~~~~~~~~~~创作不易，请点击关注、收藏

Java代码：

import java.util.Scanner;
import java.util.HashSet;
import java.util.Arrays;
 
public class Main {
 
    public static int mincostTickets(int[] costs, int[] days) {
        // 找到最后一个游玩的日子
        int lastDay = days[days.length - 1];
        // 创建动态规划表，dp[i] 表示到第 i 天的最低消费
        int[] dp = new int[lastDay + 1];
        // 用HashSet存储游玩日，便于快速查找
        HashSet<Integer> daySet = new HashSet<>();
        for (int day : days) {
            daySet.add(day);
        }
 
        // 遍历从第一天到最后一天
        for (int day = 1; day <= lastDay; day++) {
            if (!daySet.contains(day)) {
                // 如果这天不需要游玩，消费和前一天相同
                dp[day] = dp[day - 1];
            } else {
                // 否则，考虑买各种票的情况
                int cost1 = dp[Math.max(0, day - 1)] + costs[0];
                int cost3 = dp[Math.max(0, day - 3)] + costs[1];
                int cost7 = dp[Math.max(0, day - 7)] + costs[2];