美团笔试真题2023第一场（4题）

 点评：

题目总体来说偏向于中下难度

1.字符串前缀

题目描述：

现在有两个字符串S和T，你需要对S进行若干次操作，使得S是T的一个前缀（空串也是一个前缀）。每次操作可以修改S的一个字符，或者删除一个S末尾的字符。小团需要写一段程序，输出最少需要操作的次数。

输入描述

第一行一个正整数C，表示数据组数；

对于每一组数据输入两行仅包含小写字母的字符串S和T。

1≤|S|,|T|≤5X10^4 , 1≤C≤10

输出描述

对于每一组数据，输出一个整数，表示最少需要操作的次数。

样例输入

2
aba
abb
abcd
efg

样例输出

1
4

解题代码：

1. 初始化两个整数变量res和pos，res用来表示不同字符的数量，pos用来追踪当前字符的索引。
2. 计算两个字符串的长度，分别存储在maxx和minn中，其中maxx表示较长字符串的长度，minn表示较短字符串的长度。
3. 计算两个字符串长度的差值，并将结果存储在res中。这个差值表示需要添加或删除的字符数量，以使两个字符串的长度相等。
4. 从字符串末尾开始向前遍历，即从minn - 1的位置开始。
5. 对于每个位置，比较S和T中的字符，如果它们不相等，增加res的值，表示需要修改的字符数量。
6. 在每次迭代后，将pos减1，以继续比较下一个字符。
7. 最后，打印res，即需要进行的总操作次数。

#include <bits/stdc++.h>
using namespace std;
int main() {int C;cin >> C;while (C--) {string S, T;cin >> S >> T;int res = 0, pos = 0;int maxx = max(T.size(), S.size()), minn = min(T.size(), S.size());res = maxx - minn;pos = minn - 1;while (pos>=0) {if (S[pos] != T[pos])res++;pos--;}cout << res << "\n";}
}

2.小美分糖

题目描述：

某一天，小美从商店买了两种糖果，分别买了a个和b个，要分给班上n个小朋友。为了不浪费，每块糖果都得恰好分到一个小朋友。另外，两种糖果一起吃的话味道其实并不好，所以每一个小朋友都只能得到其中一种糖果。小美希望分得最少糖果的那个小朋友能得到尽量多的糖果。小美的任务是求得这个数量是多少。

输入描述

第一行一个正整数T，表示有T组数据。

对于每一组数据，输入一行n,a,b，中间用空格隔开。

1≤a,b≤10000,  2≤n≤a+b, 1≤T≤100

输出描述

对于每一组数据，输出仅一行一个整数，表示答案。

样例输入

2
5 2 3
4 7 10

样例输出

1
3

解题代码： 

1. 初始化两个整数变量l和r，它们用于表示当前查找范围的左边界和右边界。初始时，l为0，r为a + b。
2. 使用二分查找来寻找满足特定条件的最大值。在每次循环中，计算中间值mid，采用右中位数的方式（(l + r + 1) >> 1），以确保向上取整。这个中间值mid表示当前查找范围的中点。
3. 调用check(mid)函数来检查是否满足条件。check函数的目的是计算以mid为单位能够满足条件的次数。具体来说，它计算a除以x的整数部分，再加上b除以x的整数部分，以表示在长度为x的单位中，a和b分别包含多少个。
4. 如果check(mid)返回true，表示以长度为mid的单位可以满足条件，将l更新为mid，即将查找范围右移。如果返回false，表示以长度为mid的单位不能满足条件，将r更新为mid - 1，即将查找范围左移。
5. 继续二分查找，直到l和r相等，此时找到的最大mid值就是满足条件的最大单位长度。
6. 最后，输出r的值，它表示满足条件的最大单位长度。

#include <bits/stdc++.h>
using namespace std;
int n, a, b, mid;
int check(int x) {int cnt = 0;cnt = (a / x ) + (b / x);return cnt >= n;
}
int main() {int t;cin >> t;while (t--) {cin >> n >> a >> b;int l = 0, r = a + b;while (l < r) {mid = (l + r + 1) >> 1;if (check(mid))l = mid;elser = mid - 1;}cout << r << "\n";}
}

3.交通规划

题目描述：

A国有n个城市，这n个城市排成一列，依次编号为1,2,3,...,n。一开始，这n座城市之间都没有任何交通路线，于是政府打算修建一些铁路来进行交通规划。接下来T天，每一天会进行如下操作的其中一种：- “L x”：表示编号为 x 的城市与其左边的城市之间修建一条铁路。如果 x 左边没有城市或者已经修建了铁路，则无视该操作；- “R x”：表示编号为 x 的城市与其右边的城市之间修建一条铁路。如果 x 右边没有城市或者已经修建了铁路，则无视该操作；- “Q x”：表示查询 x 往左边和往右边最远能到达的城市编号。你的任务是模拟以上操作，并对于每一条“Q x”操作，输出对应的答案。

输入描述

第一行输入两个正整数 n , T ；

接下来T行，每行输入形如题面中的其中一种。

1≤n≤10000, 1≤T≤200， 1≤x≤n

输出描述

对于每一个"Q x”操作，输出一行两个正整数，分别表示 x 往左边和往右边最远能到达的城市编号，中间用空格隔开。

样例输入

3 5
Q 2
L 2
Q 2
R 2
Q 2

样例输出

2 2
1 2
1 3

解题思路：并查集

1. 首先，定义一个常数N，表示最大元素数量。声明一个整数数组p[N]，用于表示每个元素的父节点。

2. 实现find函数，它是典型的并查集中的查找函数。给定一个元素x，find(x) 函数返回其所属集合的代表元素，同时进行路径压缩，即将查找路径上的所有节点的父节点设置为代表元素。

3. 在main函数中，首先从输入读取两个整数n和T，n表示元素的总数量，T表示待执行的操作次数。

4. 初始化并查集，将每个元素的父节点初始化为自身，即p[i] = i，表示每个元素都自成一个集合。

5. 进入循环，处理T次操作。每个操作由一个字符串op和一个整数x表示。

6. 如果操作op是 "L"，则表示要将元素x与其左侧的元素合并。这里首先通过find(x)找到x所属的集合代表元素，然后判断如果x的左侧元素与x不在同一个集合，并且x不小于1，将x所属集合的代表元素设置为x左侧元素所属集合的代表元素。

7. 如果操作op是 "R"，则表示要将元素x与其右侧的元素合并。类似地，首先通过find(x)找到x所属的集合代表元素，然后判断如果x的右侧元素与x不在同一个集合，并且x不大于n-1，将x所属集合的代表元素设置为x右侧元素所属集合的代表元素。

8. 如果操作op是其他字符，这个操作是查询操作。首先初始化两个整数l和r，用于找到x所属集合的所有元素的范围。通过二分查找，首先向左找到l1，即从x开始往左一直到x所属集合的边界。然后，向右找到r，即从x开始往右一直到x所属集合的边界。输出l1和r，表示这个集合的范围。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int p[N];int find(int x) {if (p[x] != x)p[x] = find(p[x]);return p[x];
}int main() {int n, T;cin >> n >> T;for (int i = 1; i <= n; i++) {p[i] = i;}while (T--) {string op;int x;cin >> op >> x;if (op == "L" ) {if (find(x) != find(x - 1) && x >= 1)p[find(x)] = find(x - 1);} else if (op == "R") {if (find(x) != find(x + 1) && x <= n - 1) {p[find(x)] = find(x + 1);}} else {int l = 0, r = x;while (l < r) {int mid = l + r >> 1;if (find(x) == find(mid)) {r = mid;} elsel = mid + 1;}int l1 = l;l = x, r = n;while (l < r) {int mid = (l + r + 1) >> 1;if (find(x) == find(mid)) {l = mid;} elser = mid - 1;}cout << l1 <<" "<< r << "\n";}}
}

4.小美玩套娃

题目描述：

小美最近喜欢上了玩套娃。具体的，小美有 n 个套娃，第 i 个套娃的大小为 ai，内部空间为 bi(bi≤ai)。对于两个套娃x,y， x能放入y中当且仅当ax≤by ，且放入后会占据 y 大小为 ax 的内部空间，即 y 的内部空间剩下 by-ax，每个套娃只能放在另外的一个套娃内，每个套娃内部也只能放一个套娃（当然内部放的这个套娃可以内部还有套娃）。显然套娃是套的越多越好，于是小美给每个套娃定义了一个价值 ci，如果套完之后套娃 i 还剩 k 的内部空间，小美需要付出ci*k 的花费，总花费为所有套娃的花费之和，现在小美想知道最小的花费为多少。

输入描述

第一行一个正整数 n ，表示套娃的个数

接下来三行每行 n 个整数，分别为

a1,a2,...an

b1,b2,...bn

c1,c2,...,cn

1≤n,ai,bi,ci,≤100000，bi≤ai

输出描述

输出一个整数表示最小的花费

样例输入

3
5 4 3
4 2 2
3 2 1

样例输出

6

解题思路：贪心

1. 创建三个vector，a、b、c，用于存储n个元素的数据。通过循环分别读取a、b、c数组的值。

2. 创建两个二维vector t0 和 t1，每个元素是一个包含四个整数的向量，用于存储a、b、c以及元素的索引。这两个向量是用来排序的备份。

3. 对t0 和 t1 分别进行排序：

   • t0 根据a的值由小到大排序。
   • t1 根据c的值由小到大排序。

4. 初始化一个变量 ri，表示可用于装载元素的空间，初始值为n-1。

5. 初始化一个变量 res 用于记录最终的结果，初始值为0。

6. 开始一个逆序的循环，从n-1到0：

   • 在每一次循环中，首先用二分查找找到能够容纳当前元素的位置。这里通过比较 t1[i] 中的 b 值和 t0[mid] 中的 a 值来查找。
   • 如果找到了一个合适的位置 r，更新 ri 为 r-1。
   • 注意，代码中存在一些处理以避免重复使用相同的元素（t0[r][3] == t1[i][3]）以及如果 t1[i][1] 小于 t0[r][0] 则退出循环。

7. 最后，遍历 t1 数组，计算每个元素的价值（c * 剩余的容纳空间），并将结果累加到 res 中。

8. 输出 res，即为最终的答案。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
//int a[N], b[N], c[N];int main() {int n;cin >> n;vector<int> a(n);vector<int> b(n);vector<int> c(n);for (int i = 0; i < n; i++) {cin >> a[i];}for (int i = 0; i < n; i++) {cin >> b[i];}for (int i = 0; i < n; i++) {cin >> c[i];}vector<vector<int>> t0(n);vector<vector<int>> t1(n);for (int i = 0; i < n; i++) {t0[i] = {a[i], b[i], c[i], i};t1[i] = {a[i], b[i], c[i], i};}//按照a由小到大sort(t0.begin(), t0.end(), [](const vector<int> &x, const vector<int> &y) {return x[0] < y[0];});//按照c又小到大sort(t1.begin(), t1.end(), [](const vector<int> &x, const vector<int> &y) {return x[2] < y[2];});int ri = n - 1;long long res = 0;for (int i = n - 1; i >= 0; i--) {//按照c价值由大到小，和容纳空间，然后二分查找到符合的个头塞入int l = 0;int r = ri;while (l < r) {int mid = (l + r + 1 ) >> 1;if (t1[i][1] >= t0[mid][0]) {l = mid;} elser = mid - 1;}if (t0[r][3] == t1[i][3])r--;if ( t1[i][1] < t0[r][0] )break;t1[i][1] -= t0[r][0];ri = r - 1;}for (int i = 0; i < n; i++) {res += (long long)(t1[i][2] * t1[i][1]);}cout << res << "\n";
}