🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

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

🍠 饿了么秋招笔试，来啦！！！

🍥 本次饿了么笔试的难度不大，但T3出来一道写起来比较麻烦的题，建议小伙伴们可以好好尝试一下，对提升代码熟练度很有帮助

1️⃣ 数据范围较小，暴力枚举每个交换的位置

2️⃣ 考察的是手写辗转相减法，并统计运算次数

3️⃣ 并查集的模版题，但此题的难点并不在并查集上。

☕️ 01.LYA的咖啡店优化

问题描述

LYA 经营着一家热门的咖啡店。每天早晨，都有一群顾客排队等待点咖啡。每位顾客需要不同的时间来点单和等待咖啡制作。LYA 注意到，每个顾客的总等待时间包括前面所有顾客的点单和制作时间，再加上自己的点单和制作时间。

为了提高效率，LYA 想尝试调整队伍顺序。她可以选择任意两位顾客交换位置。LYA 希望通过一次交换，最大程度地减少所有顾客的总等待时间。

你能帮 LYA 找出应该交换哪两位顾客的位置，使得总等待时间最小吗？

输入格式

第一行包含一个整数 ，表示排队的顾客数量。

第二行包含 个整数 ，其中 表示第 位顾客的点单和制作时间。

输出格式

如果通过调整顺序无法减少总等待时间，输出 。

否则，输出两个整数 和 ，表示应该交换第 位和第 位顾客的位置，以最小化总等待时间。

样例输入

5
1 2 1 3 1

样例输出

2 5

数据范围

• 
• 

题解

这道题目的核心在于理解如何计算总等待时间，以及如何通过交换两个顾客的位置来减少总等待时间。让我们一步步分析：

1. 总等待时间的计算： 对于第 个顾客，他的等待时间是前面所有顾客的时间总和加上自己的时间。因此，第 个顾客对总等待时间的贡献是 。

2. 交换两个顾客的影响： 当我们交换第 和第 位顾客时（假设 ），只有这两个位置的贡献会发生变化。变化量为：

   简化后得到：

3. 解题思路：

   • 枚举所有可能的 对。
   • 计算每次交换能减少的等待时间。
   • 记录能减少最多等待时间的 对。

4. 时间复杂度： 枚举所有可能的 对的时间复杂度是 。对于 的数据范围，这是可以接受的。

• Python

import sys

def solve():
    # 读取输入
    n = int(input())
    a = list(map(int, input().split()))
    
    max_diff = 0  # 最大时间差
    best_swap = [-1, -1]  # 最佳交换位置
    
    # 枚举所有可能的交换
    for i in range(n):
        for j in range(i+1, n):
            # 计算交换 i 和 j 后的时间差
            diff = (a[i] - a[j]) * (j - i)
            if diff > max_diff:
                max_diff = diff
                best_swap = [i+1, j+1]  # 注意：输出的位置从1开始
    
    # 输出结果
    if max_diff == 0:
        print(-1)
    else:
        print(*best_swap)

# 主函数
if __name__ == "__main__":
    solve()

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        
        int maxDiff = 0;  // 最大时间差
        int[] bestSwap = {-1, -1};  // 最佳交换位置
        
        // 枚举所有可能的交换
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 计算交换 i 和 j 后的时间差
                int diff = (a[i] - a[j]) * (j - i);
                if (diff > maxDiff) {
                    maxDiff = diff;
                    bestSwap[0] = i + 1;  // 注意：输出的位置从1开始
                    bestSwap[1] = j + 1;
                }
            }
        }
        
        // 输出结果
        if (maxDiff == 0) {
            System.out.println(-1);
        } else {
            System.out.println(bestSwap[0] + " " + bestSwap[1]);
        }
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    int max_diff = 0;  // 最大时间差
    pair<int, int> best_swap = {-1, -1};  // 最佳交换位置
    
    // 枚举所有可能的交换
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // 计算交换 i 和 j 后的时间差
            int diff = (a[i] - a[j]) * (j - i);
            if (diff > max_diff) {
                max_diff = diff;
                best_swap = {i + 1, j + 1};  // 注意：输出的位置从1开始
            }
        }
    }
    
    // 输出结果
    if (max_diff == 0) {
        cout << -1 << endl;
    } else {
        cout << best_swap.first << " " << best_swap.second << endl;
    }
    
    return 0;
}

🎵 02.LYA的音乐和谐度调整

问题描述

LYA 是一位音乐制作人，她正在创作一首新歌。这首歌由 个音符对组成，每个音符对表示为 ，其中 和 分别代表两个音符的音高。

LYA 定义每个音符对的和谐度为 。为了使音乐更加和谐，她可以对每个音符对进行以下操作之一：

1. 不做任何改变
2. 将 变为
3. 将 变为

LYA 的目标是通过最少的操作次数，使所有音符对的和谐度之和最小。请你帮助 LYA 计算出最小的和谐度之和，以及达到这个最小和谐度所需的最少操作次数。

输入格式

第一行包含一个整数 ，表示音符对的数量。

接下来的 行，每行包含两个整数 和 ，表示一个音符对。

输出格式

输出两行：

• 第一行输出一个整数，表示最小的和谐度之和。
• 第二行输出一个整数，表示达到最小和谐度之和所需的最少操作次数。

样例输入

2
9 3
5 14

样例输出

0
4

样例输入

1
16 13

样例输出

0 
7

数据范围

• 
• 

题解

模拟GCD

观察题目给出的操作，可以发现这实际上是在模拟辗转相除法（欧几里得算法）的过程。

对于每对数字 ，不断地用较大的数减去较小的数，直到两个数相等。这个过程就是在找这两个数的最大公约数（GCD）。

我们不需要真正执行除法操作，而是可以直接计算商来得到操作次数。

• Python

def solve():
    n = int(input())  # 读取音符对的数量
    total_ops = 0  # 总操作次数

    for _ in range(n):
        a, b = map(int, input().split())  # 读取每个音符对
        while True:
            if a > b:
                a, b = b, a  # 确保 a <= b
            if a == b:
                break  # 如果两个数相等，退出循环
            ops = (b - 1) // a  # 计算可以进行的操作次数
            total_ops += ops  # 累加操作次数
            b -= ops * a  # 更新 b 的值

    print(0)  # 最小和谐度之和总是为 0
    print(total_ops)  # 输出总操作次数

solve()

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 读取音符对的数量
        long totalOps = 0;  // 总操作次数

        for (int i = 0; i < n; i++) {
            long a = scanner.nextLong();
            long b = scanner.nextLong();  // 读取每个音符对
            while (true) {
                if (a > b) {
                    long temp = a;
                    a = b;
                    b = temp;  // 确保 a <= b
                }
                if (a == b) {
                    break;  // 如果两个数相等，退出循环
                }
                long ops = (b - 1) / a;  // 计算可以进行的操作次数
                totalOps += ops;  // 累加操作次数
                b -= ops * a;  // 更新