2023-08-12 21:23 西北工业大学计算机类

关注

美团笔试

美团笔试（2023/8/12）

1、小美拿到了一个排列。她想知道在这个排列中，x和y是否是相邻的。你能帮帮她吗？排列是指一个长度为n的数组，其中 1 到n 每个元素恰好出现一次。

输入描述

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

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

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

保证x≠y

输出描述

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

示例1

输入：

1 4 2 3

2 4

输出

Yes

示例2：

输入：

3 4 5 1 2

3 2

输出：

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

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int x, y;
    bool flag = false;
    for (int i = 0; i < n - 1; i++) {
        if (nums[i] == x && nums[i + 1] == y)
            flag = true;
        if (nums[i] == y && nums[i + 1] == x)
            flag = true;
    }
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

输入描述

第一行输入一个正整数n，代表站的数量。第二行输入n个正整数ai，前n-1个数代表顺时针沿着公路走，i站到第i+1站之间的距离；最后一个正整数代表顺时针沿着公路走，第n站到第1站的距离。· 第三行输入两个正整数x和y，代表小美的出发地和目的地。

输出描述

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

示例1

输入

1 2 2

2 3

输出

示例2

输入

1 2 2

1 3

输出

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

int main() {
    int n;
    cin >> n;
    vector<long long> nums(n+1);
    long long sum =0,ans = 0;
    for(int i = 1; i<=n; i++){
        cin >> nums[i];
        sum += nums[i];
    }
    int x,y;
    cin >> x >> y;
    if(x > y) swap(x,y);
    for(int i= x; i < y; i++){
        ans += nums[i];
    }

    ans = min(ans,sum-ans);
    cout << ans << endl;
    return 0;
}

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

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

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

输入描述

第一行输出两个正整数n和m,代表蛋糕区域的行数和列数。

接下来的n行，每行输入m个正整数，用来表示每个区域的美味度。

1 <=n,m <=10^3

m个正整数均小于10^4

示例1

输入

2 3

1 1 4

5 1 0

输出：

#include <bits/stdc++.h>
using namespace std;
int n,m;
long long a[1005][1005];

int main() {
    cin >> n >> m;
    long long sum =0;
    for(int i =1; i<=n; i++){
        for(int j = 1; j<=m; j++){
            cin >> a[i][j];
            sum += a[i][j];
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            a[i][j] = a[i][j-1] +a[i-1][j] -a[i-1][j-1] +a[i][j];
        }
    }

    long long ans = sum;
    for(int j =1; j<=m; j++){
        ans = min(ans,abs(sum - 2*a[n][j]));
    }
    
    for(int i=1; i<=n; i++){
        ans = min(ans,abs(sum-2*a[i][m]));
    }

    cout << ans <<endl;

    return 0;
}

4、小美拿到了一个长度为n的字符串，她希望将字符串从左到右平铺成一个矩阵（先平铺第一行，然后是第二行，以此类推，矩阵有x行y列，必须保证x*y=n，即每y个字符换行，共x行）。

该矩阵的权值定义为这个矩阵的连通块数量。小美希望最终矩阵的权值尽可能小，你能帮小美求出这个最小权值吗？

注：我们定义，上下左右四个方向相邻的相同字符是连通的。

输入描述

第一行输入一个正整数n，代表字符串的长度。

第二行输入一个长度为n的、仅由小写字母组成的字符串。

1<=n<=10^4

输出描述

输出一个整数表示最小权值。

示例1

输入

aababbabb