美团数据开发工程师笔试

软件开发笔试汇总专栏：https://blog.nowcoder.net/zhuanlan/0oDWVm

题型：5道编程题

第一题

小美拿到了—个排列。她想知道在这个排列中,x和y是否是相邻的。你能帮帮她吗?

排列是指一个长度为n的数组,其中1到n每个元素恰好出现一次。

输入描述

第一行输入一个正整数n，代表排列的长度。

第二行输入n个正整数ai，代表排列的元素。

第三行输入两个正整数x和y,用空格隔开。

1≤ n ≤200000

1≤ai,x,y ≤n

保证x≠y

输出描述

如果x和y在排列中相邻，则输出"Yes"。否则输出"No"。

示例1

输入

4

1 4 2 3

2 4

输出

Yes

示例2

输入

5

3 4 5 1 2

3 2

输出No

#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 x, y;
    cin >> x >> y;

    int posX = -1, posY = -1;  // 初始位置设置为-1
    for (int i = 0; i < n; i++) {
        if (a[i] == x) posX = i;
        if (a[i] == y) posY = i;

        if (posX != -1 && posY != -1) break;  // 如果x和y的位置都找到了，就停止循环
    }

    if (abs(posX - posY) == 1) {  // 检查x和y的索引是否相差1
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

第二题

有一个环形的公路,上面共有n站，现在给定了顺时针第i站到第i+1站之间的距离(特殊的,也给出了第n站到第1站的距离)。小美想沿着公路第x站走到第y站,她想知道最短的距离是多少?

输入描述

第一行输入一个正整数n,代表站的数量。

第二行输入n个正整数ai,前n-1个数代表顺时针沿着公路走, i站到第i＋1站之间的距离;最后一个正整数代表顺时针沿着公路走,第n站到第1站的距离。

第三行输入两个正整数x和y，代表小美的出发地和目的地。

1≤n≤10^5

1≤ai≤10^9

1≤x, y≤n

输出描述

一个正整数，代表小美走的最短距离

示例1

输入

3

1 2 2

2 3

输出

2

示例2

输入

3

1 2 2

1 3

输出

2

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

int main() {
    int n;
    cin >> n;
    vector<long long> distance(n + 1, 0);  

    for (int i = 1; i <= n; i++) {
        long long d;
        cin >> d;
        distance[i] = distance[i - 1] + d;
    }

    int x, y;
    cin >> x >> y;
    if (x > y) swap(x, y);  

    long long clockwise = distance[y - 1] - distance[x - 1];
    long long counterclockwise = distance[n] - clockwise;

    cout << min(clockwise, counterclockwise) << endl;

    return 0;
}

第三题

小美有个矩形的蛋糕,共分成了n行m列，共n×m个区域,每个区域是—个小正方形,已知蛋糕每个区域都有一个美味度。她想切一刀把蛋糕切成两部分,自己吃一部分,小团吃另一部分。

小美希望两个人吃的部分的美味度之和尽可能接近,请你输出|S1-S2|的最小值。(其中S1代表小美吃的美味度,S2代表小团吃的美味度)。

请务必保证,切下来的区域都是完整的,即不能把某个小正方形切成两个小区域。

输入描述

第一行输出两个正整数n和m,代表蛋糕区域的行数和列数。接下来的n行,每行输入m 个正整数aij,用来表示每个区域的美味度。

1≤n, m≤10^3

1≤aij≤10^4

输出描述

一个整数,代表|S1-S2|的最小值。

示例1

输入

2 3

1 1 4

5 1 4

输出

0

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

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> cake(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> cake[i][j];
        }
    }

    int total = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            total += cake[i][j];
        }
    }

    int minDiff = total;

    // 沿行切
    int