大家好，我是吴师兄。

提前批开始啦！ 早点练习，准备好秋招吧。

今天分享的是 拼多多笔试真题 ，拿下它！！！

1、小C的旅行计划

题目描述

小C制定了一个详尽的旅行计划。具体来说，他打算游览 个不同的景点，并且为每个景点设定了优先级。根据规定，他必须按优先级顺序游玩，优先级高的先游玩。同时，由于景点的人气非常高，小C只能在预定的 天或者之后的每隔 天的时间里访问景点 。也就是说，他可以在 、 、 等这样的特定日子访问景点 。小C一天最多能游玩一个景点，问题是，他至少需要多少天才能完成自己的旅行计划。

输入

第一行一个整数 ，代表景点的数量。

接下来 行，每行三个整数 、 、 ：

• 表示景点 的优先级，数字越小，优先级越高。
• 是景点 的首次预定时间。
• 是重复访问的时间间隔。

输出

输出一个整数，表示小C完成旅行计划所需的最少天数。

样例

输入：
2
1 2 2
2 1 3




    


输出：
4

提示：
1号景点优先级最高，小C计划第2天游玩1号景点。由于1号景点之后的第1天（第3天）无法游玩2号景点，他将在第4天游玩2号景点。因此，总共需要4天完成计划。

题目解析

这道题要求我们找到最少的天数让小C按照优先级顺序游览所有的景点。

具体来说，每个景点都有一个初始的访问时间 X_i 和一个间隔 D_i ，表示小C只能在 X_i 这天或者之后的每隔 D_i 天访问这个景点。

我们需要按照优先级从小到大的顺序逐个游览景点，并计算小C完成全部计划所需的最少天数。

解题思路

1. 按优先级排序 ：首先，将所有景点按照优先级 P_i 进行排序，优先级越高的景点越早游玩。

2. 模拟游玩过程 ：然后，我们模拟从第1天开始游玩。对于每一个景点，如果当前时间 now 小于等于景点的最早可访问时间 X_i ，则小C可以直接在 X_i 这一天访问这个景点。如果当前时间 now 已经超过 X_i ，我们需要找出最早的可以访问的天数，并更新当前时间为该天数。

3. 计算下一个可访问时间 ：如果当前时间超过了 X_i ，我们可以通过计算 now 距离 X_i 的差值，然后找到第一个大于 now 的可访问天数。公式为：

   next_visit = ((now - X_i + D_i - 1) // D_i) * D_i + X_i
   

   其中 (now - X_i + D_i - 1) // D_i 计算出小C在 now 时间之后第一个可以访问景点的天数。

4. 更新当前时间 ：每次游玩景点后，将 now 更新为刚刚游玩的那天。

参考代码

    
n = int(input())
# 读取输入并按优先级排序
ls = sorted([tuple(map(int, input().split())) for _ in range(n)])
now = 0

for _, x, d in ls:
    if now <= x:
        # 当前时间小于等于该景点的首次预定时间，直接游玩
        now = x
    else:
        # 否则计算下一次可以游玩的时间
        now = (now - x + d - 1) // d * d + x

# 输出完成所有景点所需的最少天数
print(now)

2、小U的作业调度

题目描述

小U面临一个巨大的学业挑战。在一个学期内，他需要完成 份作业，每份作业在特定的时刻 布置，并需要 时间来完成。小U可以在任何时刻开始或切换到任何已布置但未完成的作业，但每份作业的完成耗时是它完成的实际时刻减去它被布置的时刻 。现在，小U需要一种策略来安排他的作业，以使所有作业的完成耗时总和最小。

输入

首先一行整数 ，代表作业数量。

随后 行，每行两个整数 和 ，分别表示作业的布置时刻和完成所需时间。

输出

输出一个整数，表示所有作业的最短完成耗时总和。

样例

输入：
3
1 5
5 1
7 3

输出：
10

提示：
小U可以从时刻1开始连续完成作业1（耗时5），在时刻6开始作业2（耗时2），在时刻7开始作业3（耗时3），总耗时为5+2+3=10。

题目解析

这道题的核心是寻找一种最优的调度策略，使得所有作业的完成耗时总和最小。每个作业都有一个布置时刻 t_i 和完成所需的时间 w_i 。完成耗时是作业的实际完成时刻减去其布置时刻。因此，要最小化这些耗时的总和，需要合理安排作业的执行顺序。

解题思路

1. 排序作业 ：首先将作业按照布置时刻 t_i 进行排序，确保作业按顺序处理。
2. 使用优先队列 ：在处理作业时，我们使用一个最小堆（优先队列）来选择当前最小的作业（即耗时最短的作业），这样可以最小化后续作业的等待时间。
3. 模拟调度过程 ：

• 如果没有待处理的作业，则直接跳到下一个可用的作业开始时间。
• 每次从堆中取出耗时最小的作业进行处理，更新当前时间。
• 如果当前时间不足以完成当前作业，但有其他新的作业可以加入队列，则将当前作业的剩余时间重新入堆，同时处理新加入的作业。
• 初始化当前时间 now 。
• 逐个处理每个作业：
• 记录每个作业的完成时间，并最终计算总的完成耗时。

参考代码

from heapq import heappush, heappop

def min_total_completion_time(n, tasks):
    # 将任务按布置时刻 t_i 排序
    tasks.sort()

    # 初始化当前时间和答案数组
    now = 0
    ans = [0] * n
    q = []
    pos = 0

    # 循环处理所有任务
    while pos or q:
        if not q:
            # 如果队列为空，直接跳到下一个任务的布置时刻
            heappush(q, (tasks[pos][1], pos))
            now = tasks[pos][0]
            pos += 1
        # 弹出最小耗时的任务进行处理
        w, idx = heappop(q)
        if pos == n or (pos and w <= tasks[pos][0] - now):
            # 如果当前时间足够完成这个任务
            now += w
            ans[idx] = now
        else:
            # 如果当前时间不够完成这个任务，则继续处理后续任务
            w -= tasks[pos][0] - now
            heappush(q, (w, idx))
            heappush(q, (tasks[pos][1], pos))
            now = tasks[pos][0]
            pos += 1

    # 计算所有任务的最小完成耗时总和
    return sum(ans[i] - tasks[i][0] for i in range(n))

# 输入部分
n = int(input())
tasks = [tuple(map(int, input().split())) for _ in range(n)]
print(min_total_completion_time(n, tasks))

3、小A的花坛观赏度变化

题目描述

小A有一个花坛，里面种了 盆花，这些花要么是玫瑰，要么是牡丹，从左到右依次摆放，编号从1到 。花坛的观赏度定义为玫瑰和牡丹的数量差的绝对值。现在，小A可以执行一次特殊操作，选择一段连续的花盆区间，并在这个区间内将所有玫瑰变成牡丹，牡丹变成玫瑰。小A想知道，在最多执行一次这种操作后，他的花坛可以有多少种不同的观赏度。

输入

• 第一行一个数字 ，表示花坛中有 盆花（ ）。
• 第二行 个数字，每个数字表示一盆花的种类，0表示玫瑰，1表示牡丹。

输出

• 输出一个数字，表示在最多执行一次操作后，花坛的不同观赏度的总数。

样例

输入：
2
0 1

输出：
2

提示：
- 不进行操作时，观赏度为0（1玫瑰，1牡丹）。
- 操作区间[1, 1]，花坛变为[1, 0]，观赏度为2。
- 操作区间[2, 2]，花坛变为[0, 1]，观赏度为2。
- 操作区间[1, 2]，花坛变为[1, 0]，观赏度为0。
- 结果共有2种不同的观赏度：0和2。

题目解析

这道题的核心问题是，通过对花坛中一段连续花盆区间内的花种类进行翻转，计算花坛的不同观赏度的总数。观赏度定义为玫瑰和牡丹的数量差的绝对值。为了在翻转后得到最多种不同的观赏度，我们需要分析翻转前后的观赏度变化。

解题思路

1. 计算原始观赏度 ：我们首先需要计算原始状态下的观赏度，这可以通过计算整个花坛中玫瑰和牡丹的数量差来实现。
2. 模拟翻转操作 ：我们需要模拟一次翻转操作，并计算出翻转后的观赏度。这个过程可以通过遍历所有可能的区间并计算翻转前后的观赏度变化来完成。
3. 利用前缀和优化 ：为了优化计算观赏度变化，我们可以使用前缀和来快速计算区间内的花种类数量，并通过动态规划的方式记录可能的观赏度。
4. 计算不同的观赏度 ：我们最终要统计出所有可能的观赏度，并返回其不同的数量。

参考代码

def solve(a):
    # s[n] 表示前 n 个元素的前缀和
    s = [0]
    for x in a:
        s.append(s[-1] + x)
    
    val = 0
    n = len(a)
    ans = s[n]
    
    for r in range(1, n + 1):
        # 计算翻转后的最大观赏度
        ans = max(ans, s[n] - s[r] - s[r] + r + val)
        # 更新 val 用于计算下一步的最大观赏度
        val = max(val, -r + s[r] + s[r])
    
    return ans

n = int(input())
a = list(map(int, input().split()))

# b 是 a 的反转版本
b = [1 if x == 0 else 0 for x in a]

# 计算最大和最小观赏度
mx, mn = solve(a), n - solve(b)

# 计算所有可能的不同观赏度
st = {abs(n - i - i) for i in range(mn, mx + 1)}
print(len(st))

4、简易哈希表的序列恢复

题目描述

在一个简单的哈希表实现中，我们使用一个哈希函数