京东2025.08.02笔试复盘：两道编程题思路与AC代码详解
哈喽大家好！做完 8 月 2 号的京东笔试，感觉题目质量还不错，考察的知识点也挺经典的。趁着记忆还热乎，赶紧把两道编程题的思路和代码整理出来，分享给大家，希望能帮助后面参加笔试的同学少走弯路，顺利上岸！
题目一：
题目大意
在一个餐厅里，厨师一次只能做一道菜。有 n 位客人，第 i 位客人的菜品基础制作时间是 a_i。这位客人每多等待1分钟，他的菜品制作时间就会额外增加 b_i。我们需要设计一个上菜顺序，使得所有客人的"总用餐时间"（等待时间 + 最终制作时间）之和最小。
考点分析
这道题的核心是贪心算法 (Greedy Algorithm)。看到"最优安排顺序"这类问题，我们首先可以思考能否通过一个简单的局部最优策略，来达到全局最优。这道题的贪心策略需要进行一定的数学推导来证明其正确性。
样例输入与输出
2
1 1
2 5
5
解题思路
这道题的题眼在于如何确定客人的处理顺序。一个常见的误区是优先处理制作时间 a_i 短的，或者等待系数 b_i 大的，但这些简单的策略都无法保证全局最优。
正确的姿势是使用**"邻项交换法"**来推导排序依据：
假设在我们的队列中，有两个相邻的客人 i 和 j，他们的上菜顺序是 ... -> i -> j -> ...。设在处理客人 i 之前，已经累计过去了 T 的等待时间。
顺序 i -> j 的总时间贡献：
- 客人 i 的总时间：T·b_i + a_i
- 客人 j 的总时间：（T + a_i）·b_j + a_j
- 两者时间之和（忽略公共部分 T）为：T·b_i + a_i + (T + a_i)·b_j + a_j
如果我们交换他们，顺序变为 j -> i，总时间贡献：
- 客人 j 的总时间：T·b_j + a_j
- 客人 i 的总时间：（T + a_j）·b_i + a_i
- 两者时间之和（忽略公共部分 T）为：T·b_j + a_j + (T + a_j)·b_i + a_i
为了让 i -> j 的顺序更优，需要满足：
化简这个不等式，两边消去相同的项，最终得到：
这个不等式可以写成 。这告诉我们，应该按照
的比值进行升序排序。这个结论可以推广到整个序列，证明了贪心策略的正确性。
踩坑点： 在编程实现时，直接用浮点数做除法 a/b 来排序可能会有精度问题。更稳妥的方法是使用推导出的乘法形式 a_i * b_j < a_j * b_i 作为排序的比较逻辑。
AC代码 (Python)
import sys
from functools import cmp_to_key
def solve_restaurant():
"""
贪心策略，通过邻项交换法证明排序依据。
根据样例分析，等待时间由前面客人的基础制作时间累加而成。
"""
try:
n = int(sys.stdin.readline())
clients = []
for _ in range(n):
a, b = map(int, sys.stdin.readline().split())
clients.append((a, b))
except (IOError, ValueError):
return
# 排序规则: a1/b1 < a2/b2 <=> a1*b2 < a2*b1
clients.sort(key=cmp_to_key(lambda c1, c2: c1[0] * c2[1] - c2[0] * c1[1]))
MOD = 1000000009
total_production_time = 0
cumulative_base_time = 0
for base_time, wait_coeff in clients:
wait_time = cumulative_base_time
actual_production_time = (base_time + wait_time * wait_coeff)
total_production_time = (total_production_time + actual_production_time) % MOD
cumulative_base_time = (cumulative_base_time + base_time) % MOD
print(total_production_time)
if __name__ == "__main__":
solve_restaurant()
题目二：
题目大意
一个机器人从无限大网格的 (0, 0) 点出发，每次只能向上、向左、向右移动一格，且走过的格子不能重复。求机器人恰好走 n 步的路径方案数是多少，结果对 10^9+7 取模。
考点分析
这道题是典型的动态规划 (Dynamic Programming) 问题，并且由于 n 的数据范围极大，需要结合矩阵快速幂 (Matrix Exponentiation) 进行优化。
样例输入与输出
2
7
解题思路
寻找递推关系： 首先，我们尝试计算 n 较小时的方案数，寻找规律。
- n=0: 停在原地，算 1 种方案。f(0)=1。
- n=1: 可以向上、向左、向右，共 3 种方案。f(1)=3。
- n=2:
- 从 (0,1) 出发（第一步向上）：可以继续向上、向左、向右，3 种 (上上, 上左, 上右)。
- 从 (1,0) 出发（第一步向右）：可以向上、向右，2 种 (右上, 右右)。
- 从 (-1,0) 出发（第一步向左）：可以向上、向左，2 种 (左上, 左左)。
- 总共 3+2+2=7 种方案。f(2)=7。
有了序列 f(0)=1, f(1)=3, f(2)=7。大胆猜测递推关系：f(n) = 2·f(n−1) + f(n−2)。
验证一下：f(2) = 2·f(1) + f(0) = 2·3 + 1 = 7。完美符合！
矩阵快速幂优化： 找到了递推公式 f(n) = 2f(n−1) + f(n−2)。由于 n 可以达到 10^9，直接循环递推会超时。这是一个标准的线性递推式，可以使用矩阵快速幂进行加速。
我们将递推关系转化为矩阵形式：
$ =
$
这个矩阵 $ $ 就是我们的"转移矩阵" M。
通过连续应用这个关系，我们可以得到：
现在问题就转化为了求 M 的 n−1 次幂。使用矩阵快速幂算法，我们可以在 O(log n) 的时间复杂度内求出 M^(n−1)。
得到 后，最终结果 f(n) = a·f(1) + b·f(0)。
AC代码 (Python)
import sys
def solve_robot_path():
"""
动态规划找递推关系 + 矩阵快速幂优化
f(n) = 2*f(n-1) + f(n-2)
"""
try:
n = int(sys.stdin.readline())
except (IOError, ValueError):
return
MOD = 1000000007
if n == 0:
print(1)
return
if n == 1:
print(3)
return
def matrix_multiply(A, B):
C = [[0, 0], [0, 0]]
C[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD
C[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD
C[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD
C[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD
return C
def matrix_power(matrix, exponent):
result_matrix = [[1, 0], [0, 1]]
base_matrix = matrix
while exponent > 0:
if exponent % 2 == 1:
result_matrix = matrix_multiply(result_matrix, base_matrix)
base_matrix = matrix_multiply(base_matrix, base_matrix)
exponent //= 2
return result_matrix
transition_matrix = [[2, 1], [1, 0]]
power_n_minus_1 = n - 1
result_matrix = matrix_power(transition_matrix, power_n_minus_1)
a, b = result_matrix[0][0], result_matrix[0][1]
answer = (a * 3 + b * 1) % MOD
print(answer)
if __name__ == "__main__":
solve_robot_path()
互联网复盘刷题集合
查看5道真题和解析
投递百度等公司10个岗位