【秋招突围】2024届秋招-美团笔试题-第一套

🍭 大家好这里是清隆Coding ，一枚热爱算法的程序员

✨ 本系列打算持续跟新 美团 春秋招笔试题**汇总～

👏 感谢大家的 点赞💗 和 关注➕ 和 小花花🌸

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

🌸 01.K小姐的排列问题

问题描述

K小姐得到了一个由 到 组成的排列,她想知道排列中是否存在两个指定的数 和 相邻。

现在请你帮助K小姐判断,给定的 和 是否在排列中相邻。

输入格式

第一行包含一个正整数 ,表示排列的长度。

第二行包含 个正整数 ,表示这个排列。

第三行包含两个正整数 和 ,表示需要判断是否相邻的两个数。

输出格式

如果 和 在排列中相邻,输出 Yes,否则输出 No。

样例输入

4
1 3 4 2
2 4

样例输出

Yes

数据范围

• 
• 
• 保证

题解

本题可以直接模拟。我们遍历整个排列,判断相邻的两个数是否为 和 即可。

具体实现时,可以用两个指针 和 分别指向当前判断的两个相邻的位置,初始时 ,。然后不断右移这两个指针,直到 到达排列的末尾。

在遍历的过程中,如果 且 ,或者 且 ,就说明找到了相邻的 和 ,可以直接输出 Yes 并结束程序。

如果遍历完整个排列都没有找到相邻的 和 ,就输出 No。

时间复杂度 ,空间复杂度 。

参考代码

• Python

# 读取输入的排列长度 n
n = int(input())

# 读取排列 a
a = list(map(int, input().split()))

# 读取需要判断是否相邻的两个数 x 和 y
x, y = map(int, input().split())

# 初始化两个指针 pre 和 nxt，分别指向排列中的相邻位置
pre, nxt = 0, 1

# 遍历整个排列，直到 nxt 到达排列末尾
while nxt < n:
    # 检查当前相邻的两个数是否为 x 和 y 或 y 和 x
    if (a[pre] == x and a[nxt] == y) or (a[pre] == y and a[nxt] == x):
        # 如果找到相邻的 x 和 y，输出 "Yes" 并结束程序
        print("Yes")
        exit(0)
    # 将指针右移，检查下一个相邻的位置
    pre += 1
    nxt += 1

# 如果遍历完整个排列都没有找到相邻的 x 和 y，输出 "No"
print("No")

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入的排列长度 n
        int n = sc.nextInt();
        
        // 读取排列 a
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        // 读取需要判断是否相邻的两个数 x 和 y
        int x = sc.nextInt(), y = sc.nextInt();
        
        // 初始化两个指针 pre 和 nxt，分别指向排列中的相邻位置
        int pre = 0, nxt = 1;
        
        // 遍历整个排列，直到 nxt 到达排列末尾
        while (nxt < n) {
            // 检查当前相邻的两个数是否为 x 和 y 或 y 和 x
            if ((a[pre] == x && a[nxt] == y) || (a[pre] == y && a[nxt] == x)) {
                // 如果找到相邻的 x 和 y，输出 "Yes" 并结束程序
                System.out.println("Yes");
                return;
            }
            // 将指针右移，检查下一个相邻的位置
            pre++;
            nxt++;
        }
        
        // 如果遍历完整个排列都没有找到相邻的 x 和 y，输出 "No"
        System.out.println("No");
    }
}

• Cpp

#include <iostream>
using namespace std;

const int N = 2e5 + 5; // 定义常量 N，表示最大排列长度
int n, x, y; // 定义变量 n, x, y
int a[N]; // 定义数组 a，存储排列

int main() {
    // 读取输入的排列长度 n
    cin >> n;
    
    // 读取排列 a
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 读取需要判断是否相邻的两个数 x 和 y
    cin >> x >> y;
    
    // 初始化两个指针 pre 和 nxt，分别指向排列中的相邻位置
    int pre = 0, nxt = 1;
    
    // 遍历整个排列，直到 nxt 到达排列末尾
    while (nxt < n) {
        // 检查当前相邻的两个数是否为 x 和 y 或 y 和 x
        if ((a[pre] == x && a[nxt] == y) || (a[pre] == y && a[nxt] == x)) {
            // 如果找到相邻的 x 和 y，输出 "Yes" 并结束程序
            cout << "Yes" << endl;
            return 0;
        }
        // 将指针右移，检查下一个相邻的位置
        pre++, nxt++;
    }
    
    // 如果遍历完整个排列都没有找到相邻的 x 和 y，输出 "No"
    cout << "No" << endl;
    return 0;
}

🍡 02.LYA的游乐园之旅

问题描述

LYA是一位勇敢好奇的小女孩。这个周末,她来到了一个大型的环形游乐园游玩。游乐园中有 个游乐项目,编号从 到 。

园区内共有 条道路,每条道路连接两个游乐项目。其中前 条道路按顺时针依次连接相邻的游乐项目,最后一条道路连接第 个和第 个游乐项目。每条道路都有一个距离值 。

LYA计划从第 个游乐项目开始游玩,最后到达第 个游乐项目。她想知道从 走到 的最短距离是多少。你能帮帮她吗?

输入格式

第一行包含一个正整数 ,表示游乐项目的数量。

第二行包含 个正整数,其中前 个数 分别表示第 个游乐项目到第 个游乐项目、第 个游乐项目到第 个游乐项目、……、第 个游乐项目到第 个游乐项目之间道路的距离,最后一个数 表示第 个游乐项目到第 个游乐项目之间道路的距离。

第三行包含两个正整数 和 ,分别表示LYA游玩的起点项目编号和终点项目编号。

输出格式

输出一个整数,表示LYA从第 个游乐项目到第 个游乐项目的最短距离。

样例输入

3
1 2 3
1 2

样例输出

1

样例输入

5
2 1 3 4 1
1 3

样例输出

3

数据范围

题解

本题可以通过前缀和的方式求解。我们可以先计算出从第 个游乐项目出发,到达每个游乐项目的距离前缀和。然后根据起点 和终点 的相对位置,分别计算顺时针和逆时针的距离,取两者的最小值即可。

具体步骤如下:

1. 读入游乐项目数量 和各道路的距离 。

2. 计算前缀和数组 ,其中 表示从第 个游乐项目到第 个游乐项目的距离之和。

3. 读入起点 和终点 。如果 ,则交换 和 的值。

4. 计算顺时针距离 。

5. 计算逆时针距离 。

6. 输出 和 中的最小值。

时间复杂度 ,空间复杂度 。

参考代码

• Python

# 读取游乐项目的数量 n
n = int(input())

# 读取各条道路的距离 d
d = list(map(int, input().split()))

# 读取起点 x 和终点 y
x, y = map(int, input().split())

# 初始化前缀和数组 pre，长度为 n+1
pre = [0] * (n + 1)

# 计算前缀和数组 pre
for i in range(1, n + 1):
    pre[i] = pre[i - 1] + d[i - 1]

# 如果起点 x 大于终点 y，交换 x 和 y
if x > y:
    x, y = y, x

# 计算顺时针距离 dist1
dist1 = pre[y - 1] - pre[x - 1]

# 计算逆时针距离 dist2
dist2 = pre[n] - dist1

# 输出顺时针和逆时针距离的最小值
print(min(dist1, dist2))

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取游乐项目的数量 n
        int n = sc.nextInt();
        
        // 读取各条道路的距离 d
        int[] d = new int[n];
        for (int i = 0; i < n; i++) {
            d[i] = sc.nextInt();
        }
        
        // 读取起点 x 和终点 y
        int x = sc.nextInt();
        int y = sc.nextInt();
        
        // 初始化前缀和数组 pre，长度为 n+1
        long[] pre = new long[n + 1];
        
        // 计算前缀和数组 pre
        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + d[i - 1];
        }
        
        // 如果起点 x 大于终点 y，交换 x 和 y
        if (x > y) {
            int temp = x;
            x = y;
            y = temp;
        }
        
        // 计算顺时针距离 dist1
        long dist1 = pre[y - 1] - pre[x - 1];
        
        // 计算逆时针距离 dist2
        long dist2 = pre[n] - dist1;
        
        // 输出顺时针和逆时针距离的最小值
        System.out.println(Math.min(dist1, dist2));
    }
}

• Cpp

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

int main() {
    // 读取游乐项目的数量 n
    int n;
    cin >> n;
    
    // 读取各条道路的距离 d
    vector<int> d(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
    
    // 读取起点 x 和终点 y
    int x, y;
    cin >> x >> y;
    
    // 初始化前缀和数组 pre，长度为 n+1
    vector<long long> pre(n + 1);
    
    // 计算前缀和数组 pre
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + d[i - 1];
    }
    
    // 如果起点 x 大于终点 y，交换 x 和 y
    if (x > y) {
        swap(x, y);
    }
    
    // 计算顺时针距离 dist1
    long long dist1 = pre[y - 1] - pre[x - 1];
    
    // 计算逆时针距离 dist2
    long long dist2 = pre[n] - dist1;
    
    // 输出顺时针和逆时针距离的最小值
    cout << min(dist1, dist2) << endl;
    
    return 0;
}

🌲 03.A先生的遗产分配

问题描述

A先生是一位成功的商人，他拥有一片面积为 的矩形土地。在他临终之前，他决定将这片土地分给他的两个儿子。每块土地都有一个价值 ，代表第 行第 列的土地的价值。

为了公平起见，A先生希望将土地分成两个完整的矩形部分，使得两部分的总价值之差最小。你能帮助A先生找到最优的分配方案吗？

输入格式

第一行包含两个正整数 和 ，分别表示土地的行数和列数。

接下来的 行，每行包含 个正整数 ，表示第 行第 列的土地的价值。

输出格式

输出一个整数，表示两个儿子分到的土地总价值之差的最小值。

样例输入

5 5
1 1 1 1 1 
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

样例输出

5

数据范围

• 
• 

题解

本题可以使用前缀和的思想来解决。我们可以预处理出一个二维前缀和数组 ，其中 表示左上角为 ，右下角为 的子矩阵的元素和。

然后我们枚举分割线的位置，可以是横向的，也可以是纵向的。对于横向的分割线，我们可以计算出上半部分的总价值为 ，下半部分的总价值为 ，它们的差的绝对值就是当前分割方案的代价。纵向的分割线同理。

我们在所有可能的分割方案中取最小值，就是最终的答案。

时间复杂度为 ，空间复杂度为 。

参考代码

• Cpp

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

int main() {
    // 读取土地的行数 n 和列数 m
    int n, m;
    cin >> n >> m;
    
    // 初始化前缀和数组 pre，大小为 (n+1) x (m+1)
    vector<vector<long long>> pre(n + 1, vector<long long>(m + 1));
    
    // 读取土地的价值并计算前缀和数组 pre
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> pre[i][j];
            pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
        }
    }
    
    // 初始化最小差值为正无穷大
    long long ans = 1e18;
    
    // 枚举横向分割线的位置
    for (int i = 1; i < n; ++i) {
        // 计算上半部分和下半部分的价值差
        long long dist1 = pre[i][m];
        long long dist2 = pre[n][m] - dist1;
        // 更新最小差值
        ans = min(ans, abs(dist1 - dist2));
    }
    
    // 枚举纵向分割线的位置
    for (int j = 1; j < m; ++j) {
        // 计算左半部分和右半部分的价值差
        long long dist1 = pre[n][j];
        long long dist2 = pre[n][m] - dist1;
        // 更新最小差值
        ans = min(ans, abs(dist1 - dist2));
    }
    
    // 输出最小差值
    cout << ans << endl;
    
    return 0;
}

• Python

# 读取土地的行数 n 和列数 m
n, m = map(int, input().split())

# 初始化前缀和数组 pre，大小为 (n+1) x (m+1)
pre = [[0] * (m + 1) for _ in range(n + 1)]

# 读取土地的价值并计算前缀和数组 pre
for i in range(1, n + 1):
    a = list(map(int, input().split()))
    for j in range(1, m + 1):
        # 计算前缀和
        pre[i][j] = a[j - 1] + pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1]

# 初始化最小差值为正无穷大
ans = float('inf')

# 枚举横向分割线的位置
for i in range(1, n):
    # 计算上半部分和下半部分的价值差
    dist1 = pre[i][m]
    dist2 = pre[n][m] - dist1
    # 更