美团笔试 - 0824

24年秋招【技术】第三场

放瓶子

题面

小美初始位于 $(a, b)$ 位置，一维平面上有 $n$ 个瓶子，每个瓶子的位置为 $(x_i, y_i)$。小美每次可以向上、下、左、右移动一格，每次移动的代价为 $1$，小美需要移动到第一个瓶子的位置上，然后拿起瓶子把它放到 $(c, d)$ 位置，每次最多只能拿一个瓶子，请问最少需要多少代价才能把所有瓶子都放到 $(c, d)$ 位置上。

输入描述:
第一行四个整数 $a, b, c, d(-10^9 \leq a, b, c, d \leq 10^9)$，表示小美初始位置和瓶子需要放置的位置。
接下来一行一个整数 $n(1 \leq n \leq 10^5)$，表示瓶子的数量。
接下来 $n$ 行，每行两个整数 $x_i, y_i(-10^9 \leq x_i, y_i \leq 10^9)$，表示第 $i$ 个瓶子的位置。

输出描述:
输出一个整数，表示最少需要多少代价。

贪心。

我们需要计算小美从初始位置到每个瓶子的距离，然后从每个瓶子到目标位置的距离，最后将所有瓶子移动到目标位置的总距离。关键是要找出一个最优的瓶子访问顺序，以最小化总移动距离。

最有访问顺序：找一个 离 $(a, b)$ 点距离 + $(c, d)$ 点距离最大 的点作为第一个点，其他点的移动距离都是 到 $(c, d)$ 点距离*2

1. 计算每个瓶子到位置 $(a, b)$ 和 $(c, d)$ 的距离之和，取最大。

2. 计算剩余瓶子到位置 $(c, d)$ 的距离。

3. 累加所有移动的距离即可。

最大乘积

题面

小美有三个数字 $a,b,c$，他每次操作可以选择一个数字将其 $+1$，最多可以操作 $k$ 次，小美想知道 $a \times b \times c$ 的最大值是多少？

由于这个数字可能很大，因此你需要输出答案对 $10^9 + 7$ 取模后的结果。

输入描述：
第一行四个正整数 $a,b,c,k(1 \leq a,b,c,k \leq 10^{18})$ 表示数字和操作次数。

输出描述：
输出一个整数表示答案。

贪心。

应该将所有的操作次数用在最小的数字上，直到它等于或超过第二小的数字，然后再考虑第二小的数字，以此类推。这样可以最大化三个数字的乘积。

1. 将三个数字排序，使 $a ≤ b ≤ c$。

2. 计算将 $a$ 增加到 $b$ 所需的操作次数，如果 $k$ 足够，就执行这些操作。

3. 如果还有剩余操作次数，尝试将 $a$ 和 $b$ 同时增加到 $c$。

4. 如果还有剩余操作次数，平均分配到 $a$、$b$、$c$ 上。

5. 计算最终的 $a × b × c$，并对 $10^9 + 7$ 取模。

def max_product(a, b, c, k):
    MOD = 10**9 + 7
    
    # 步骤1：排序确保 a <= b <= c
    nums = sorted([a, b, c])
    a, b, c = nums
    
    # 步骤2：将 a 增加到 b
    diff = b - a
    if k >= diff:
        a = b
        k -= diff
    else:
        a += k
        return (a * b * c) % MOD
    
    # 步骤3：将 a 和 b 增加到 c
    diff = (c - a) * 2
    if k >= diff:
        a = c
        b = c
        k -= diff
    else:
        increase = k // 2
        a += increase
        b += increase
        if k % 2 == 1:
            a += 1
        return (a * b * c) % MOD
    
    # 步骤4：平均分配剩余的操作次数
    increase = k // 3
    a += increase
    b += increase
    c += increase
    
    # 处理剩余的1或2次操作
    if k % 3 == 1:
        a += 1
    elif k % 3 == 2:
        a += 1
        b += 1
    
    # 步骤5：计算最终结果并取模
    return (a * b * c) % MOD

# 读取输入
a, b, c, k = map(int, input().split())

# 计算并输出结果
result = max_product(a, b, c, k)
print(result)

牛牛商店

题面

牛牛商店里只卖两种商品，"牛可乐"和"牛马克"。

现在有 $n$ 个人来到商店购物，第 $i$ 个人有喜好区间 $[l_i, r_i]$ 和购买目标商品，他只看货架上位于区间里的商品，并从中挑选 $k_i$ 个保质期最长的牛可乐或者牛马克走（如果有多个商品保质期相同，他会拿走区间中靠前的那个）。你能告诉牛牛每个人买走的商品编号吗？

输入描述：
第一行输入两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 10^5)$ 代表来牛牛商店购物的人数和商品数量。
第二行输入 $m$ 个整数 $a_1, a_2 \ldots a_m$ $(1 \leq a_i < 10^9)$ 代表商品的保质期。
第三行输入 $m$ 个整数 $b_1, b_2 \ldots, b_m$ $(0 \leq b_i \leq 1)$ 代表商品的种类，其中，$b_i = 0$ 代表"牛可乐"，$b_i = 1$ 代表"牛马克"。
此后 $n$ 行，第 $i$ 行输入四个整数 $l_i, r_i, t_i$ 和 $k_i$ $(1 \leq l_i \leq r_i \leq m; 0 \leq t_i \leq 1; 1 \leq k_i \leq m)$ 代表第 $i$个人的喜好区间、购买商品种类和购买数量。其中，$t_i = 0$ 代表他想要买"牛可乐"，$t_i = 1$ 代表他想要买"牛马克"。

输出描述：
输出 $n$ 行，第 $i$ 行输出至多 $k_i$ 个整数，代表第 $i$ 个人购买的商品编号（如果有多个商品保质期相同，输出编号较小的那个）。你需要按照从小到大的顺序依次输出；如果没有买到足够的商品，使用一个 $-1$ 替代。

核心是高效地在指定区间内找出保质期最长的特定类型商品。考虑到数据规模 $(n,m ≤ 10^5)$，我们需要一个能够在 $O(log n)$ 时间内查询区间最大值的数据结构。即线段树。

1. 构建两个线段树，分别用于存储牛可乐和牛马茶的保质期信息。

2. 在线段树中，每个节点存储该区间内的最大保质期和对应的最小商品编号。

3. 对于每个顾客的查询：

   • 在对应类型的线段树上查询指定区间 $[l_i, r_i]$ 内的最大保质期商品。
   • 如果找到符合条件的商品，记录其编号，并在线段树中将该商品的保质期设为 $-1$（表示已售出）。
   • 重复上述过程 $k_i$ 次或直到无法找到更多符合条件的商品。