09.14团子(已改编)-三语言题解
💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历
👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸
✨ 笔试合集传送们 -> 🧷学长刷题笔记
🍒 本专栏已收集
140+套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞
🍥 本次难度不小，最后一题是倍增+预处理，写起来比较麻烦细节容易错，建议非竞赛选手尝试暴力骗分
1️⃣ 小学数学题，每次用最大的桶装
2️⃣ 枚举题，对于每个玩家分别暴力向左和向右拓展
3️⃣ 二分答案，这题最无脑也最容易写的做法就是二分啦，直接贪心容易出错
4️⃣ 贪心，当然也可以用DP(比较麻烦)
5️⃣ 倍增+预处理，一看就是打竞赛的人出的题，笔试中并不常见，建议非竞赛选手直接尝试暴力骗分
💧 01.K小姐的装水问题 评测链接🔗
问题描述
在一个美丽的小镇上，K小姐经营着一家水上运输公司。她有三个不同容量的桶，分别为 单位。最近，小镇的居民请求她帮助运输
单位的水到镇外的湖泊。每次运输时，K小姐可以选择使用任意一个桶装水，装满后将水送到目的地，然后返回继续装水。为了提高效率，K小姐希望知道她至少需要多少趟才能完成这个运输任务。
输入格式
第一行包含四个正整数 ，分别表示待运输的水量和三个桶的容量。
输出格式
输出一个整数，表示将 单位的水装完至少需要跑多少趟。
样例输入
4 2 2 1
样例输出
2
数据范围
题解
结论题
可以发现每次都用最大的桶装即可，最终答案为
参考代码
- Python
def min_trips(n, a, b, c):
# 找出最大的桶容量
max_capacity = max(a, b, c)
# 计算所需趟数并向上取整
trips = (n + max_capacity - 1) // max_capacity
return trips
# 输入处理
n, a, b, c = map(int, input().split())
# 输出结果
print(min_trips(n, a, b, c))
- Java
import java.util.Scanner;
public class MinTrips {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 输入待运输水量和三个桶的容量
int n = scanner.nextInt();
int a = scanner.nextInt();
int b = scanner.nextInt();
int c = scanner.nextInt();
// 找出最大的桶容量
int maxCapacity = Math.max(a, Math.max(b, c));
// 计算所需趟数并向上取整
int trips = (n + maxCapacity - 1) / maxCapacity;
// 输出结果
System.out.println(trips);
}
}
- Cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n, a, b, c;
// 输入待运输水量和三个桶的容量
cin >> n >> a >> b >> c;
// 找出最大的桶容量
int maxCapacity = max(a, max(b, c));
// 计算所需趟数并向上取整
int trips = (n + maxCapacity - 1) / maxCapacity;
// 输出结果
cout << trips << endl;
return 0;
}
✨ 02.捉迷藏游戏的胜利时间 评测链接🔗
问题描述
在一个神秘的森林中，K小姐、小蓝和小绿正在进行一场捉迷藏的游戏。他们的当前位置分别用字母表示，其他位置可能是空地（用 '*' 表示）或障碍物（用 '#' 表示）。寻找方可以每秒移动到相邻的空地，而躲藏方则无法移动。当寻找方移动到躲藏方的位置时，躲藏方就被找到，游戏结束。
在这场游戏中，K小姐、小蓝和小绿都希望能尽快找到对方。现在，我们需要计算出当他们分别作为寻找方时，能够获胜所需的最少时间。如果某个寻找方无法找到任何躲藏方，则输出 -1。
输入格式
输入包含一个仅由字符 '*'、'#'、'R'、'B'、'G' 组成的字符串 ，其中
表示 K小姐 的位置，
表示小蓝的位置，
表示小绿的位置。字符串的长度
满足
。
输出格式
输出一行，包含三个整数，分别表示 K小姐、小蓝和小绿作为寻找方时能够获胜的最少时间。如果无法获胜，则直接输出 -1。
样例输入
R***B**G
样例输出
4 3 3
数据范围
- 字符串长度
的范围为
。
- 字符 '
', '
', '
' 各自只出现一次。
题解
模拟
对于每种字符，分别尝试向左向右拓展, 遇到障碍物即可停止，计算出各自的最小距离。
参考代码
- Python
def find_min_time(s):
# 定义角色
characters = 'RBG'
n = len(s)
results = []
for ch in characters:
# 找到当前角色的位置
idx = s.find(ch)
i, j = idx - 1, idx + 1
count = 1
found = False
while i >= 0 or j < n:
# 检查左边是否找到其他角色
if i >= 0 and s[i] in characters:
found = True
break
# 如果左边是空地，继续向左移动
if i >= 0 and s[i] == '*':
i -= 1
# 检查右边是否找到其他角色
if j < n and s[j] in characters:
found = True
break
# 如果右边是空地，继续向右移动
if j < n and s[j] == '*':
j += 1
count += 1
# 如果没有找到其他角色，返回 -1
if not found:
count = -1
results.append(count)
return results
# 示例输入
s = "R***B**G"
print(find_min_time(s)) # 输出: [4, 3, 3]
- Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
char[] characters = {'R', 'B', 'G'};
int n = s.length();
for (char ch : characters) {
// 找到当前角色的位置
int idx = s.indexOf(ch);
int i = idx - 1, j = idx + 1;
int count = 1;
boolean found = false;
while (i >= 0 || j < n) {
// 检查左边是否找到其他角色
if (i >= 0 && charactersContains(s.charAt(i), characters)) {
found = true;
break;
}
// 如果左边是空地，继续向左移动
if (i >= 0 && s.charAt(i) == '*') i--;
// 检查右边是否找到其他角色
if (j < n && charactersContains(s.charAt(j), characters)) {
found = true;
break;
}
// 如果右边是空地，继续向右移动
if (j < n && s.charAt(j) == '*') j++;
count++;
}
// 如果没有找到其他角色，返回 -1
if (!found) count = -1;
System.out.print(count + " ");
}
}
private static boolean charactersContains(char c, char[] characters) {
for (char ch : characters) {
if (ch == c) return true;
}
return false;
}
}
- Cpp
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
cin >> s;
string characters = "RBG";
int n = s.size();
for (char ch : characters) {
// 找到当前角色的位置
int idx = s.find(ch);
int i = idx - 1, j = idx + 1;
int count = 1;
bool found = false;
while (i >= 0 || j < n) {
// 检查左边是否找到其他角色
if (i >= 0 && characters.find(s[i]) != string::npos) {
found = true;
break;
}
// 如果左边是空地，继续向左移动
if (i >= 0 && s[i] == '*') i--;
// 检查右边是否找到其他角色
if (j < n && characters.find(s[j]) != string::npos) {
found = true;
break;
}
// 如果右边是空地，继续向右移动
if (j < n && s[j] == '*') j++;
count++;
}
// 如果没有找到其他角色，返回 -1
if (!found) count = -1;
cout << count << " ";
}
return 0;
}
🧩 03.砖块合成与收集 评测链接🔗
问题描述
在一个小镇上，K小姐正在进行一项有趣的砖块收集活动。她手中有 个红砖、
个蓝砖和
个绿砖。根据镇上的规定，每
个红砖可以合成
个蓝砖，而每
个蓝砖可以合成
个绿砖。值得注意的是，砖块只能正向合成，不能反向分解。
K小姐希望收集到尽可能多的完整套砖块，每套包含 个红砖、
个蓝砖和
个绿砖。请计算 K小姐最多可以收集多少套完整的砖块。
输入格式
每个测试文件均包含多组测试数据。第一行输入一个整数 ，代表数据组数。每组测试数据描述如下：
在一行上输入五个整数 ，分别表示红砖、蓝砖和绿砖的数量及合成的比例。
输出格式
对于每一组测试数据，在一行上输出一个整数，代表 K小姐最多可以收集到的砖块套数。
样例输入
2
1 2 3 4 2
10 2 1 4 2
样例输出
1
2
数据范围
- 每组数据中的
的值均在
到
之间。
- 合成比例
的值均在
到
题解
二分答案
假定当前的答案是 ，对于红砖来说将
的部分全部合成蓝砖。 蓝砖同理，将多余的部分全部合成绿砖。 如果最后绿砖的数量
说明当前答案可以满足，尝试更大的答案，否则尝试更小的答案。 上述的过程可以用二分来实现，时间复杂度
参考代码
- Python
import sys
# 从标准输入读取数据
input = lambda: sys.stdin.readline().strip()
# 读取测试用例数量
T = int(input())
# 遍历每个测试用例
for _ in range(T):
# 读取每组数据的参数
a, b, c, x, y = map(int, input().split())
# 初始化二分查找的范围
lo, hi = 0, a
# 检查是否可以收集到 mid 套完整砖块
def check(mid, a, b, c):
# 计算多余的红砖数量并合成蓝砖
diff = a - mid
b += diff // x
# 检查蓝砖是否足够
diff = b - mid
if diff < 0:
return False
# 计算多余的蓝砖数量并合成绿砖
c += diff // y
# 检查绿砖是否足够
diff = c - mid
if diff < 0:
return False
return True
# 二分查找最大可收集套数
while lo < hi:
mid = (lo + hi + 1) >> 1
if check(mid, a, b, c):
lo = mid
else:
hi = mid - 1
# 输出结果
print(lo)
- Java
import java.util.Scanner;
public class BrickCollection {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取测试用例数量
int T = sc.nextInt();
// 遍历每个测试用例
for (int t = 0; t < T; t++) {
// 读取每组数据的参数
long a = sc.nextLong();
long b = sc.nextLong();
long c = sc.nextLong();
long x = sc.nextLong();
long y = sc.nextLong();
// 初始化二分查找的范围
long lo = 0;
long hi = a;
// 检查是否可以收集到 mid 套完整砖块
while (lo < hi) {
long mid = (lo + hi + 1) / 2;
if (canCollect(mid, a, b, c, x, y)) {
lo = mid;
} else {
hi = mid - 1;
}
}
// 输出结果
System.out.println(lo);
}
sc.close();
}
private static boolean can剩余60%内容，订阅专栏后可继续查看/也可单篇购买
本专栏短期内不再更新，请勿继续订阅
投递快手等公司10个岗位 >
