09.14团子(已改编)-三语言题解

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编,如果和你实际看到的题面描述不一样请理解,做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅,你们的支持是我们创作的最大动力 💞

alt

🍥 本次难度不小,最后一题是倍增+预处理,写起来比较麻烦细节容易错,建议非竞赛选手尝试暴力骗分

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%内容,订阅专栏后可继续查看/也可单篇购买

本专栏短期内不再更新,请勿继续订阅

全部评论

相关推荐

05-05 21:45
已编辑
广州大学 Java
点赞 评论 收藏
分享
05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
点赞 评论 收藏
分享
评论
2
8
分享

创作者周榜

更多
牛客网
牛客企业服务