2023 美团笔试题 0415
笔试时间：2023年04月15日 春招
备注：第五题暂未有题解。
第一题
题目：字符串的前缀
现在有两个字符串S和T，你需要对S进行若干次操作，使得S是T的一个前缀（空串也是一个前缀）。每次操作可以修改S的一个字符，或者删除一个S末尾的字符。小团需要写一段程序，输出最少需要操作的次数。
输入描述
第一行一个正整数C，表示数据组数；
对于每一组数据输入两行仅包含小写字母的字符串S和T。
输出描述
对于每一组数据，输出一个整数，表示最少需要操作的次数。
样例输入
2
aba
abb
abcd
efg
样例输出
1
4
提示：
第一组数据，可以修改最后一个字母，使得S=abb，是T的一个前缀；第二组数据，需要将S整个串删除，操作次数为4。
参考题解
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <string>
using namespace std;
int main() {
int C;
cin >> C;
cin.ignore(); // Ignore the newline after reading C
for (int i = 0; i < C; ++i) {
string S, T;
getline(cin, S);
getline(cin, T);
int res = 0;
int pos = 0;
if (S.length() > T.length()) {
res = S.length() - T.length();
pos = T.length() - 1;
} else {
pos = S.length() - 1;
}
bool flag = false;
while (pos >= 0) {
if (!flag) {
if (S[pos] == T[pos]) {
flag = true;
} else {
res++;
}
} else {
if (S[pos] != T[pos]) {
res++;
}
}
pos--;
}
cout << res << endl;
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int C = scanner.nextInt();
scanner.nextLine(); // Consume newline
for (int i = 0; i < C; ++i) {
String S = scanner.nextLine();
String T = scanner.nextLine();
int res = 0;
int pos = 0;
if (S.length() > T.length()) {
res = S.length() - T.length();
pos = T.length() - 1;
} else {
pos = S.length() - 1;
}
boolean flag = false;
while (pos >= 0) {
if (!flag) {
if (S.charAt(pos) == T.charAt(pos)) {
flag = true;
} else {
res++;
}
} else {
if (S.charAt(pos) != T.charAt(pos)) {
res++;
}
}
pos--;
}
System.out.println(res);
}
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
C = int(input())
for _ in range(C):
S = input()
T = input()
res, pos = 0, 0
if len(S) > len(T):
res = len(S) - len(T)
pos = len(T) - 1
else:
pos = len(S) - 1
flag = False
while pos >= 0:
if not flag:
if S[pos] == T[pos]:
flag = True
else:
res += 1
else:
if S[pos] != T[pos]: res += 1
pos -= 1
print(res)
第二题
题目：小美分糖
某一天，小美从商店买了两种糖果，分别买了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
提示：
第一组数据，每个小朋友都恰好分得一个糖果；第二组数据，可以分成：（3个第一种，4个第一种，5个第二种，5个第二种），这样第一个小朋友分得最少，没有其他方案使得分得最少的那个小朋友的糖果数量更大。
参考题解
二分答案。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
using namespace std;
bool check(long long x, long long n, long long a, long long b) {
long long r1 = min(a, b);
long long r2 = max(a, b);
long long cnt = 1;
r2 -= x;
cnt += (r2 / x) + (r1 / x);
return cnt >= n;
}
int main() {
int T;
cin >> T;
for (int t = 0; t < T; ++t) {
long long n, a, b;
cin >> n >> a >> b;
long long l = 0;
long long r = max(a, b);
while (l < r) {
long long mid = (l + r + 1) >> 1;
if (check(mid, n, a, b)) {
l = mid;
} else {
r = mid - 1;
}
}
cout << r << endl;
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
public class Main {
public static boolean check(long x, long n, long a, long b) {
long r1 = Math.min(a, b);
long r2 = Math.max(a, b);
long cnt = 1;
r2 -= x;
cnt += (r2 / x) + (r1 / x);
return cnt >= n;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt();
for (int t = 0; t < T; ++t) {
long n = scanner.nextLong();
long a = scanner.nextLong();
long b = scanner.nextLong();
long l = 0;
long r = Math.max(a, b);
while (l < r) {
long mid = (l + r + 1) >> 1;
if (check(mid, n, a, b)) {
l = mid;
} else {
r = mid - 1;
}
}
System.out.println(r);
}
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
T = int(input())
for _ in range(T):
n, a, b = map(int, input().strip().split(" "))
def check(x):
r1, r2 = min(a,b), max(a,b)
cnt = 1
r2 -= x
cnt += (r2 //x) + (r1 //x)
'''一个人分x 其他人x+1， 如果可以就ok'''
return cnt >= n
l, r = 0, max(a,b)
while l < r:
mid = (l + r + 1) >> 1
if check(mid):l = mid
else: r = mid - 1
print(r)
第三题
题目：交通规则
A国有n个城市，这n个城市排成一列，依次编号为1,2,3,...,n。一开始，这n座城市之间都没有任何交通路线，于是政府打算修建一些铁路来进行交通规划。接下来T天，每一天会进行如下操作的其中一种：- “L x”：表示编号为 x 的城市与其左边的城市之间修建一条铁路。如果 x 左边没有城市或者已经修建了铁路，则无视该操作；- “R x”：表示编号为 x 的城市与其右边的城市之间修建一条铁路。如果 x 右边没有城市或者已经修建了铁路，则无视该操作；- “Q x”：表示查询 x 往左边和往右边最远能到达的城市编号。你的任务是模拟以上操作，并对于每一条“Q x”操作，输出对应的答案。
输入描述
第一
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2023秋招各大笔试题汇总，c++，java，python多种语言分析，解答。
