美团
美团¶
在线笔试
90分钟：10道选择 + 3道编程
第一题¶
题目描述¶
小红（R）、小蓝（B）和小绿（G）正在一个字符串上玩捉迷藏。他们所在的位置用对应字母表示，其他位置为空地（*）或障碍（#）。 寻找方可以每秒移动一个位置，躲藏方不能移动。当寻找方移动到躲藏方的位置时，躲藏方被认为被找到。但是在过程中，双方均不可以移动到障碍上。
当一个人作为寻找方，另外两个人作为躲藏方时，只要寻找方找到一个躲藏方即认为游戏胜利。
请计算三个人分别作为寻找方时，能够使游戏胜利所需的最少时间。
输入描述
在一行上输入一个仅由 “ *#RGB ” 组成的字符串 ，保证 “ RGB ” 各只出现一次。
输出描述
在一行上输出三个整数，代表小红、小蓝和小绿作为寻找方时，能够获胜的最少时间；如果无法获胜，则直接输出 -1 。
示例 1：
输入：
R***B**G
输出：
4 3 3
这个问题可以看作是一个最短路径问题，其中障碍物“#”不可通过，其他位置可以通过。我们需要计算每个人（R、B、G）作为寻找方时，找到其他两个人中的一个所需的最少时间。
使用广度优先搜索（BFS）是解决这个问题的理想方法，因为 BFS 能够在无权图（每一步移动的代价相同）中找到从起点到终点的最短路径。
解决方案：¶
- 建模问题：字符串表示地图，
R、B、G分别表示三个人的位置。*表示可通过的空地，#表示障碍物。 - BFS搜索：我们可以从每个寻找方的位置出发，使用BFS计算从该点到其他两个人位置的最短距离。
- 最终结果：对于每个人作为寻找方，取找到两个躲藏方中的最短时间。
步骤：¶
- 从输入字符串中分别找到
R、B和G的索引位置。 - 对于每个寻找方（
R、B、G），执行一次 BFS，记录从当前寻找方到其他两个人的最短路径。 - 取最小的非负路径作为答案。如果找不到任何路径，则输出
-1。
代码¶
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class HideAndSeek {
public static void main(String[] args) {
// 使用 Scanner 读取输入
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine(); // 从标准输入读取一行
scanner.close(); // 关闭输入流
// 调用 findMinimumTimes 函数，返回三个整数结果
int[] result = findMinimumTimes(input);
// 输出结果
System.out.println(result[0] + " " + result[1] + " " + result[2]);
}
// 计算每个人作为寻找方时的最短时间
public static int[] findMinimumTimes(String map) {
// 获取各个角色的索引位置
int R = map.indexOf('R');
int B = map.indexOf('B');
int G = map.indexOf('G');
// 分别计算 R, B, G 作为寻找方时的最短时间
int rTime = bfs(map, R, B, G);
int bTime = bfs(map, B, R, G);
int gTime = bfs(map, G, R, B);
return new int[] {rTime, bTime, gTime};
}
// BFS 函数，计算从 start 开始到 target1 或 target2 的最短距离
public static int bfs(String map, int start, int target1, int target2) {
int n = map.length();
boolean[] visited = new boolean[n]; // 记录已访问的位置
Queue<int[]> queue = new LinkedList<>(); // 队列用于 BFS，保存当前索引和步数
queue.offer(new int[]{start, 0}); // {当前位置，距离}
visited[start] = true; // 标记起始位置已访问
while (!queue.isEmpty()) {
int[] current = queue.poll();
int position = current[0]; // 当前索引位置
int steps = current[1]; // 当前步数
// 如果当前位置是目标位置之一，则返回步数
if (position == target1 || position == target2) {
return steps;
}
// 检查左右两个邻居
if (position - 1 >= 0 && !visited[position - 1] && map.charAt(position - 1) != '#') {
queue.offer(new int[]{position - 1, steps + 1});
visited[position - 1] = true;
}
if (position + 1 < n && !visited[position + 1] && map.charAt(position + 1) != '#') {
queue.offer(new int[]{position + 1, steps + 1});
visited[position + 1] = true;
}
}
// 如果找不到任何目标，则返回 -1
return -1;
}
}
第二题¶
题目描述¶
小美有 a 个红砖、b 个蓝砖和 c 个绿砖。每 x 个红砖可以合成 1 个蓝砖，每 y 个蓝砖可以合成 1个绿砖。砖块只能正向合成，不能反向分解。
一套砖块包含 个红砖、 个蓝砖和 个绿砖。请计算小美最多可以收集多少套砖块。
输入描述： 每个测试文件均包含多组测试数据。第一行输入一个整数T(1<=T<=100000) 代表数据组数，每组测试数据描述如下： 在一行上输入五个整数 a, b, c, x, y(0<=a, b, c <=1000000000, 1<=x,y<=1000000000)，分别表示红砖、蓝砖、绿砖的数量及合成的比例。
输出描述： 对于每一组测试数据，在一行上输出一个整数，代表小美最多可以收集到的砖块套数。
示例：
输入： 2 1 2 3 4 2 10 2 1 4 2
输出： 1 2
问题分析：¶
- 初始资源：有
a个红砖、b个蓝砖、c个绿砖。 - 合成规则：
- 每
x个红砖可以合成 1 个蓝砖。 - 每
y个蓝砖可以合成 1 个绿砖。
- 每
- 目标：最大化套数
k，使得在资源限制和合成规则下，可以收集到k套砖块。
解题思路：¶
我们需要计算在合成规则和初始资源的限制下，最大可能的套数 k。由于砖块只能正向合成，不能反向分解，我们需要谨慎地计算每一步的资源消耗。
使用二分查找：
- 搜索范围：
[0, 最大可能的套数]，其中最大可能的套数可以是a + b + c。 - 判断条件：对于一个中间值
k，判断是否能收集到k套砖块。
判断函数 canMake(k) 的实现：
-
计算需要的额外绿砖数：
needGreen = max(0, k - c)-
计算合成绿砖需要的蓝砖数：
-
totalBlueNeededForGreen = needGreen * y -
计算需要的总蓝砖数：
-
totalBlueNeeded = k (用于套装) + totalBlueNeededForGreen -
计算需要的额外蓝砖数：
-
needBlue = max(0, totalBlueNeeded - b) -
计算合成蓝砖需要的红砖数：
-
totalRedNeededForBlue = needBlue * x -
计算需要的总红砖数：
-
totalRedNeeded = k (用于套装) + totalRedNeededForBlue -
判断资源是否足够：
-
totalRedNeeded <= a
示例计算：¶
以第一组测试数据 1 2 3 4 2 为例：
-
目标套数
k = 1：needGreen = max(0, 1 - 3) = 0totalBlueNeededForGreen = 0 * 2 = 0totalBlueNeeded = 1 + 0 = 1needBlue = max(0, 1 - 2) = 0totalRedNeededForBlue = 0 * 4 = 0totalRedNeeded = 1 + 0 = 1- 判断：
totalRedNeeded (1) <= a (1)，满足条件，可以收集到 1 套。 -
目标套数
k = 2： -
needGreen = max(0, 2 - 3) = 0 totalBlueNeededForGreen = 0 * 2 = 0totalBlueNeeded = 2 + 0 = 2needBlue = max(0, 2 - 2) = 0totalRedNeededForBlue = 0 * 4 = 0totalRedNeeded = 2 + 0 = 2- 判断：
totalRedNeeded (2) <= a (1)，不满足条件，不能收集到 2 套。
代码¶
import java.util.Scanner;
public class BrickSets {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt(); // 读取测试数据组数
while (T-- > 0) {
long a = scanner.nextLong(); // 红砖数量
long b = scanner.nextLong(); // 蓝砖数量
long c = scanner.nextLong(); // 绿砖数量
long x = scanner.nextLong(); // 合成一个蓝砖所需的红砖数量
long y = scanner.nextLong(); // 合成一个绿砖所需的蓝砖数量
// 使用二分查找计算最多可以形成多少套砖块
long left = 0, right = a + b + c; // 初始范围
while (left < right) {
long mid = left + (right - left + 1) / 2; // 取中间值，避免溢出
if (canMake(mid, a, b, c, x, y)) {
left = mid; // 如果能收集到 mid 套，则尝试更多套数
} else {
right = mid - 1; // 如果不能收集到 mid 套，则减少套数
}
}
// 输出结果
System.out.println(left);
}
scanner.close();
}
// 判断是否能够收集到 k 套砖块
public static boolean canMake(long k, long a, long b, long c, long x, long y) {
// 需要额外的绿砖
long needGreen = Math.max(0, k - c); // 需要合成的绿砖数量
// 合成绿砖所需的蓝砖
long totalBlueNeededForGreen = needGreen * y;
// 需要的总蓝砖数
long totalBlueNeeded = k + totalBlueNeededForGreen;
// 需要额外的蓝砖
long needBlue = Math.max(0, totalBlueNeeded - b);
// 合成蓝砖所需的红砖
long totalRedNeededForBlue = needBlue * x;
// 需要的总红砖数
long totalRedNeeded = k + totalRedNeededForBlue;
// 判断红砖是否足够
if (totalRedNeeded > a) {
return false;
}
return true;
}
}
第三题¶
题目描述¶
小美正在一张有向但不一定连通的图上玩游戏。这张图包含 n 个点，第 i 个点的权值为 a_i，当小美从 i 移动到 Nexti 时，游戏规则如下： - 如果 a_Nexti > a_i，小美的金币将增加 x； - 如果 a_Nexti <= a_i ，小美的金币将增加 y。 小美会提出 q 次询问，每个询问从某个点 u 出发，移动不超过 k 步，最多能获得多少金币。
输入描述：
第一行输入四个整数 n, q, x, y (1<=n, q <= 2* 100000, -1000000<=x, y<=1000000)代表图上点的数量、询问的次数、规则中金币的增加量。
第二行输入 n 个整数 Next1, Next2, ..., Nextn (1<=Nexti <=n) 表示第 个节点下一步的位置。 第三行输入 n 个整数 a_1, a_2, ... , a_n (1<=a_i<=1000000) ，表示第 i 个节点的权值。 此后 q 行，每行输入两个整数 u, k (1<=u<=n,1<=k<=1000000000)代表一次询问的起始点和步数限制。
输出描述： 对于每一次询问，在一行上输出一个整数，代表最多能获得的金币数量。
示例： 输入：
4 5 -2 3
2 3 4 1
5 10 3 2
1 1
1 2
1 4
2 4
2 7
0
1
4
6
8
说明： 对于示例： 对于第一次询问，走一步会扣除 2金币，但是可以选择站在原地不走； 对于第二次询问，走一步时金币数量减至 -2，走两步金币数量变更为 -2+3=1。
问题分析¶
-
关键问题：当步数 kkk 较小时，我们需要精确地计算在有限步数内能够获得的最大金币数。之前的代码在处理环时，直接使用了环的总金币数和最大子段和，没有考虑剩余步数的限制，导致结果不准确。
-
解决方案：为了准确计算在剩余步数内能够获得的最大金币数，我们需要在进入环后，模拟最多 \(\min(k, 2 \times \text{环的长度})\) 步的移动。这是因为在环内，最坏情况下，我们需要遍历两次环才能找到最大的子段和。
代码¶
import java.util.*;
public class XiaoMeiGame {
static int n, q;
static long x, y;
static int[] Next;
static int[] a;
static int[] status; // 0: 未访问, 1: 访问中, 2: 已访问
static int[] step; // step[node]: 到达节点的步数
static long[] coins; // coins[node]: 到达节点的累计金币数
static int[] cycleId; // cycleId[node]: 节点所属的环的编号
static int[] cyclePos;// cyclePos[node]: 节点在环中的位置
static List<List<Integer>> cycles = new ArrayList<>();
static List<Long> cycleTotalCoins = new ArrayList<>();
static List<Integer> cycleLength = new ArrayList<>();
static List<long[]> cycleGains = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
q = sc.nextInt();
x = sc.nextLong();
y = sc.nextLong();
Next = new int[n];
a = new int[n];
for (int i = 0; i < n; i++) {
Next[i] = sc.nextInt() - 1; // 调整为从0开始的索引
}
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
status = new int[n];
step = new int[n];
coins = new long[n];
cycleId = new int[n];
cyclePos = new int[n];
Arrays.fill(cycleId, -1);
// 预处理
for (int i = 0; i < n; i++) {
if (status[i] == 0) {
dfs(i, 0, 0, new HashMap<>());
}
}
// 读取查询并输出结果
for (int i = 0; i < q; i++) {
int u = sc.nextInt() - 1; // 调整为从0开始的索引
long k = sc.nextLong();
long ans = getMaxCoins(u, k);
System.out.println(ans);
}
}
// 深度优先搜索，寻找环并预处理
static void dfs(int u, int currStep, long currCoins, Map<Integer, Integer> map) {
status[u] = 1;
step[u] = currStep;
coins[u] = currCoins;
map.put(u, currStep);
int v = Next[u];
long gain = (a[v] > a[u]) ? x : y;
if (status[v] == 0) {
dfs(v, currStep + 1, currCoins + gain, map);
} else if (status[v] == 1) {
// 找到一个环
List<Integer> cycle = new ArrayList<>();
List<Long> gains = new ArrayList<>();
long totalCoins = 0;
int node = v;
do {
int nextNode = Next[node];
long edgeGain = (a[nextNode] > a[node]) ? x : y;
totalCoins += edgeGain;
gains.add(edgeGain);
cycle.add(node);
cycleId[node] = cycles.size();
node = nextNode;
} while (node != v);
cycles.add(cycle);
cycleTotalCoins.add(totalCoins);
cycleLength.add(cycle.size());
cycleGains.add(gains.stream().mapToLong(Long::longValue).toArray());
}
// 已访问完节点u
status[u] = 2;
}
// 计算查询的最大金币数
static long getMaxCoins(int u, long k) {
long maxCoins = 0;
int currNode = u;
long currCoins = 0;
long steps = 0;
Map<Integer, Long> visited = new HashMap<>();
while (steps < k && !visited.containsKey(currNode)) {
visited.put(currNode, steps);
int nextNode = Next[currNode];
long gain = (a[nextNode] > a[currNode]) ? x : y;
currCoins += gain;
steps++;
currNode = nextNode;
maxCoins = Math.max(maxCoins, currCoins);
if (cycleId[currNode] != -1) {
break;
}
}
if (steps == k || cycleId[currNode] == -1) {
return maxCoins;
}
// 处理环
int cid = cycleId[currNode];
int len = cycleLength.get(cid);
long[] gains = cycleGains.get(cid);
long totalCycleGain = cycleTotalCoins.get(cid);
long remainingSteps = k - steps;
// 模拟环内移动，最多遍历2次环，避免时间过长
int maxSimulateSteps = (int) Math.min(remainingSteps, 2 * len);
long tempCoins = currCoins;
int tempNodeIndex = -1;
for (int i = 0; i < cycles.get(cid).size(); i++) {
if (cycles.get(cid).get(i) == currNode) {
tempNodeIndex = i;
break;
}
}
for (int i = 0; i < maxSimulateSteps; i++) {
int idx = (tempNodeIndex + i) % len;
tempCoins += gains[idx];
maxCoins = Math.max(maxCoins, tempCoins);
}
// 如果剩余步数大于模拟的步数且环的总增益为正，可以通过完整循环获得更多金币
if (remainingSteps > maxSimulateSteps && totalCycleGain > 0) {
long cyclesCount = (remainingSteps - maxSimulateSteps) / len;
tempCoins += cyclesCount * totalCycleGain;
maxCoins = Math.max(maxCoins, tempCoins);
}
return maxCoins;
}
}
代码说明¶
-
在
dfs函数中：- 记录了每个环的增益数组
gains，用于后续计算最大金币数。 -
在
getMaxCoins函数中： -
步骤 1：在进入环之前，逐步移动，并记录累计金币数
currCoins和已访问节点，直到步数用完或进入环。 - 步骤 2：如果在步数用完之前进入了环，模拟在环内的移动。
- 模拟步数：为了保证效率，最多模拟 min(剩余步数,2×环的长度)\min(\text{剩余步数}, 2 \times \text{环的长度})min(剩余步数,2×环的长度) 步。
- 模拟过程：从当前节点开始，按照环的顺序累加金币数，并更新
maxCoins。
- 步骤 3：如果剩余步数超过了模拟的步数，并且环的总增益为正，那么可以通过完整循环环来获得更多金币。
- 计算可以完整循环的次数，并累加相应的金币数。
- 记录了每个环的增益数组
过了30%