✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线100+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

题目一：餐厅点餐时间优化

1️⃣：将所有客人按照基础制作时间与等待系数的比值升序排序

2️⃣：依次计算每个客人的总用餐时间并累加等待时间

3️⃣：使用贪心策略保证全局最优解

难度：中等

这道题的关键在于理解等待时间对总时间的影响，通过数学推导发现应该按照 的比值来排序。贪心策略保证了局部最优能达到全局最优，时间复杂度为 。

题目二：机器人路径探索

1️⃣：分析机器人移动规律，发现递推关系

2️⃣：构造转移矩阵并使用矩阵快速幂优化计算

3️⃣：在 时间内求解大规模问题

难度：中等偏难

这道题结合了组合数学和矩阵运算，需要先找出递推规律，然后使用矩阵快速幂来处理大数据范围。关键是理解路径计数的本质和矩阵快速幂的应用。

01. 餐厅点餐时间优化

问题描述

小基 在一家高档餐厅工作，这家餐厅有一个特殊的规定：厨师只能同时制作一道菜，所以除了第一位客人之外，其他客人都需要等待前面的客人点的菜制作完成。

现在有 位客人需要点餐，第 位客人点的菜需要制作 分钟。

由于厨房设备的特殊性，第 位客人每等待 分钟，他的菜品制作时间就会额外增加 分钟（因为菜品变得复杂或需要重新处理）。

作为餐厅经理，小基 需要安排客人点餐的先后顺序，使每位客人的总用餐时间（包括等待时间）之和最小。

输入格式

第一行包含一个正整数 ，表示客人数量（）。

接下来 行，每行包含两个正整数 （），分别表示第 位客人菜品的基础制作时间和等待系数。

输出格式

输出一行一个整数，表示最小总时间。如果答案过大，需要对 取模。

样例输入

2
1 1
2 5

样例输出

5

数据范围

• 
• 

样例	解释说明
样例1	如果第2位客人先点餐，第1位客人后点餐：第2位客人用时2分钟，第1位客人用时1+2×1=3分钟，总计5分钟

题解

这道题的核心是找到最优的排队顺序。乍一看可能会觉得应该让制作时间短的客人先点餐，但这样想是不对的。

关键观察是：每个客人的总时间包括等待时间和制作时间。如果一个客人等待了 分钟，那么他的总时间是 。

假设我们有两个客人 和 ，考虑这两种安排顺序：

1. 先安排客人 ，再安排客人
2. 先安排客人 ，再安排客人

对于顺序1：客人 用时 ，客人 用时 ，总时间为 。

对于顺序2：客人 用时 ，客人 用时 ，总时间为 。

要让顺序1更优，需要满足：

化简得到：，即

这说明我们应该按照 的升序来排列客人。

算法步骤：

1. 将所有客人按照 升序排序
2. 依次处理每个客人，累计等待时间和总时间
3. 对结果取模

时间复杂度为 ，主要消耗在排序上。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

def solve():
    n = int(input())
    clients = []
    
    # 读取客人信息
    for i in range(n):
        a, b = map(int, input().split())
        clients.append((a, b))
    
    # 按照 a[i]/b[i] 升序排序，使用交叉相乘避免浮点数
    clients.sort(key=lambda x: x[0] * 1.0 / x[1])
    
    MOD = 1000000009
    total_wait = 0  # 累计等待时间
    result = 0      # 总答案
    
    for cook_time, wait_coeff in clients:
        # 当前客人的总时间 = 等待时间 * 等待系数 + 制作时间
        result = (result + total_wait * wait_coeff + cook_time) % MOD
        # 更新累计等待时间
        total_wait = (total_wait + cook_time) % MOD
    
    print(result)

if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 1000000009;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<pair<ll, ll>> clients(n);
    
    // 读取客人信息
    for (int i = 0; i < n; i++) {
        cin >> clients[i].first >> clients[i].second;
    }
    
    // 按照 a[i]/b[i] 升序排序，使用交叉相乘避免浮点数误差
    sort(clients.begin(), clients.end(), [](const pair<ll, ll>& x, const pair<ll, ll>& y) {
        return x.first * y.second < y.first * x.second;
    });
    
    ll total_wait = 0;  // 累计等待时间
    ll result = 0;      // 总答案
    
    for (const auto& client : clients) {
        ll cook_time = client.first;
        ll wait_coeff = client.second;
        
        // 当前客人的总时间 = 等待时间 * 等待系数 + 制作时间
        result = (result + total_wait * wait_coeff + cook_time) % MOD;
        // 更新累计等待时间
        total_wait = (total_wait + cook_time) % MOD;
    }
    
    cout << result << "\n";
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    static final long MOD = 1000000009L;
    
    static class Client {
        long cookTime;
        long waitCoeff;
        
        Client(long cookTime, long waitCoeff) {
            this.cookTime = cookTime;
            this.waitCoeff = waitCoeff;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        List<Client> clients = new ArrayList<>();
        
        // 读取客人信息
        for (int i = 0; i < n; i++) {
            String[] parts = br.readLine().split(" ");
            long cookTime = Long.parseLong(parts[0]);
            long waitCoeff = Long.parseLong(parts[1]);
            clients.add(new Client(cookTime, waitCoeff));
        }
        
        // 按照 a[i]/b[i] 升序排序
        clients.sort((x, y) -> {
            return Long.compare(x.cookTime * y.waitCoeff, y.cookTime * x.waitCoeff);
        });