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

     点评：

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

    1.字符串前缀

    题目描述：

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

    输入描述

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

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

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

    输出描述

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

    样例输入

    1. 2
    2. aba
    3. abb
    4. abcd
    5. efg

    样例输出

    1. 1
    2. 4

    解题代码：

    1. 初始化两个整数变量res和pos，res用来表示不同字符的数量，pos用来追踪当前字符的索引。
    2. 计算两个字符串的长度，分别存储在maxx和minn中，其中maxx表示较长字符串的长度，minn表示较短字符串的长度。(前提条件是S的长度大于T)
    3. 计算两个字符串长度的差值，并将结果存储在res中。这个差值表示需要添加或删除的字符数量，以使两个字符串的长度相等。(前提条件是S的长度大于T)
    4. 从字符串末尾开始向前遍历，即从minn - 1的位置开始。
    5. 对于每个位置，比较S和T中的字符，如果它们不相等，增加res的值，表示需要修改的字符数量。
    6. 在每次迭代后，将pos减1，以继续比较下一个字符。
    7. 最后，打印res，即需要进行的总操作次数。
    1. #include 
    2. using namespace std;
    3.  
    4. int main() {
    5. 	int C;
    6. 	cin >> C;
    7. 	while (C--) {
    8. 		string S, T;
    9. 		cin >> S >> T;
    10. 		int res = 0, pos = 0;
    11. 		int maxx = 0, minn = 0;
    12. 		if (S.size() > T.size()) {
    13. 			maxx = S.size();
    14. 			minn = T.size();
    15. 			res = maxx - minn;
    16. 			pos = minn - 1;
    17. 		} else {
    18. 			minn = S.size();
    19. 			pos = minn - 1;
    20. 		}
    21.  
    22. 		while (pos >= 0) {
    23. 			if (S[pos] != T[pos])
    24. 				res++;
    25. 			pos--;
    26. 		}
    27. 		cout << res << "\n";
    28. 	}
    29. }

    2.小美分糖

    题目描述：

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

    输入描述

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

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

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

    输出描述

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

    样例输入

    1. 2
    2. 5 2 3
    3. 4 7 10

    样例输出

    1. 1
    2. 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的值，它表示满足条件的最大单位长度。
    1. #include 
    2. using namespace std;
    3. int n, a, b, mid;
    4. int check(int x) {
    5. 	int cnt = 0;
    6. 	cnt = (a / x ) + (b / x);
    7. 	return cnt >= n;
    8. }
    9. int main() {
    10. 	int t;
    11. 	cin >> t;
    12. 	while (t--) {
    13. 		cin >> n >> a >> b;
    14. 		int l = 0, r = a + b;
    15. 		while (l < r) {
    16. 			mid = (l + r + 1) >> 1;
    17. 			if (check(mid))
    18. 				l = mid;
    19. 			else
    20. 				r = mid - 1;
    21. 		}
    22. 		cout << r << "\n";
    23. 	}
    24. }

    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 往左边和往右边最远能到达的城市编号，中间用空格隔开。

    样例输入

    1. 3 5
    2. Q 2
    3. L 2
    4. Q 2
    5. R 2
    6. Q 2

    样例输出

    1. 2 2
    2. 1 2
    3. 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，表示这个集合的范围。

    1. #include 
    2. using namespace std;
    3. const int N = 1e6 + 10;
    4. int p[N];
    5.  
    6. int find(int x) {
    7. 	if (p[x] != x)
    8. 		p[x] = find(p[x]);
    9. 	return p[x];
    10. }
    11.  
    12. int main() {
    13. 	int n, T;
    14. 	cin >> n >> T;
    15. 	for (int i = 1; i <= n; i++) {
    16. 		p[i] = i;
    17. 	}
    18. 	while (T--) {
    19. 		string op;
    20. 		int x;
    21. 		cin >> op >> x;
    22. 		if (op == "L" ) {
    23. 			if (find(x) != find(x - 1) && x >= 1)
    24. 				p[find(x)] = find(x - 1);
    25. 		} else if (op == "R") {
    26. 			if (find(x) != find(x + 1) && x <= n - 1) {
    27. 				p[find(x)] = find(x + 1);
    28. 			}
    29. 		} else {
    30. 			int l = 0, r = x;
    31. 			while (l < r) {
    32. 				int mid = l + r >> 1;
    33. 				if (find(x) == find(mid)) {
    34. 					r = mid;
    35. 				} else
    36. 					l = mid + 1;
    37. 			}
    38. 			int l1 = l;
    39. 			l = x, r = n;
    40. 			while (l < r) {
    41. 				int mid = (l + r + 1) >> 1;
    42. 				if (find(x) == find(mid)) {
    43. 					l = mid;
    44. 				} else
    45. 					r = mid - 1;
    46. 			}
    47. 			cout << l1 <<" "<< r << "\n";
    48. 		}
    49. 	}
    50. }

    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

    输出描述

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

    样例输入

    1. 3
    2. 5 4 3
    3. 4 2 2
    4. 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，即为最终的答案。

    1. #include 
    2. using namespace std;
    3. const int N = 1e6 + 10;
    4. //int a[N], b[N], c[N];
    5.  
    6. int main() {
    7. 	int n;
    8. 	cin >> n;
    9. 	vector<int> a(n);
    10. 	vector<int> b(n);
    11. 	vector<int> c(n);
    12. 	for (int i = 0; i < n; i++) {
    13. 		cin >> a[i];
    14. 	}
    15. 	for (int i = 0; i < n; i++) {
    16. 		cin >> b[i];
    17. 	}
    18. 	for (int i = 0; i < n; i++) {
    19. 		cin >> c[i];
    20. 	}
    21. 	vectorint>> t0(n);
    22. 	vectorint>> t1(n);
    23. 	for (int i = 0; i < n; i++) {
    24. 		t0[i] = {a[i], b[i], c[i], i};
    25. 		t1[i] = {a[i], b[i], c[i], i};
    26. 	}
    27. 	//按照a由小到大
    28. 	sort(t0.begin(), t0.end(), [](const vector<int> &x, const vector<int> &y) {
    29. 		return x[0] < y[0];
    30. 	});
    31. 	//按照c又小到大
    32. 	sort(t1.begin(), t1.end(), [](const vector<int> &x, const vector<int> &y) {
    33. 		return x[2] < y[2];
    34. 	});
    35. 	int ri = n - 1;
    36. 	long long res = 0;
    37. 	for (int i = n - 1; i >= 0; i--) {
    38. 		//按照c价值由大到小，和容纳空间，然后二分查找到符合的个头塞入
    39. 		int l = 0;
    40. 		int r = ri;
    41. 		while (l < r) {
    42. 			int mid = (l + r + 1 ) >> 1;
    43. 			if (t1[i][1] >= t0[mid][0]) {
    44. 				l = mid;
    45. 			} else
    46. 				r = mid - 1;
    47. 		}
    48. 		if (t0[r][3] == t1[i][3])
    49. 			r--;
    50. 		if ( t1[i][1] < t0[r][0] )
    51. 			break;
    52. 		t1[i][1] -= t0[r][0];
    53. 		ri = r - 1;
    54. 	}
    55. 	for (int i = 0; i < n; i++) {
    56. 		res += (long long)(t1[i][2] * t1[i][1]);
    57. 	}
    58. 	cout << res << "\n";
    59. }

  • 相关阅读:
    k8s简单架构图
    软考系统架构之案例篇(Redis相关概念)
    读像火箭科学家一样思考笔记02_与不确定性共舞（下）
    文本和二进制混合存储
    Onnx精度转换 FP32-＞FP16
    数字政府一网统管体系下的运维管理软件应用探讨
    llama2-13的训练模型流程咨询
    智慧公厕领先品牌:卫生、智能、环保
    【C++】鱼的一生， 智能指针的实现
    iOS App Store上传项目报错 缺少隐私政策网址(URL)解决方法
  • 原文地址：https://blog.csdn.net/m0_57071296/article/details/133992153