【秋招笔试】9.07美团秋招改编题(研发岗)

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试

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

✨ 本系列打算持续跟新 春秋招笔试题

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

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新

🍄 题面描述等均已改编,如果和你笔试题看到的题面描述不一样请理解,做法和题目本质基本不变。

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

alt

🍠 美团秋招笔试,来啦!!!

🍥 本次的第三题有点问题,不清楚是题意还是其他有没描述清楚什么,目前没看到通过率 100% 的解法。

1️⃣ 简单的分奇偶考虑

2️⃣ 可以DFS,也可以直接for循环模拟,只需要统计儿子的数量即可。

3️⃣ 线段树,但目前没有通过率 100 的做法,需要完成 区间+-区间求最大/最小区间统计0的数量等操作,这些信息需要线段树来维护,如果有正确解法,后续会更新~

📚 01.LYA的魔法书架

问题描述

LYA是一位热爱魔法的少女。她有一个神奇的书架,上面摆放着 本魔法书。每本书都有一个魔力值 。LYA发现,当书架上所有书的魔力值都是奇数或都是偶数时,书架会释放出强大的魔法。

为了激活书架的魔法,LYA可以对任意一本书施加增强魔法。每次施法,她可以选择一本书,将其魔力值增加任意正整数 )。但是,每次施法都需要消耗能量,消耗的能量值等于该书原本的魔力值加上增加的魔力值,即

现在,LYA想知道要使书架上的所有书魔力值要么全为奇数,要么全为偶数,她最少需要消耗多少能量。

输入格式

第一行一个整数 ),表示魔法书的数量。

第二行 个整数,第 个数为 ),表示第 本书的魔力值。

输出格式

一个整数,表示 LYA 使书架上的所有书魔力值要么全为奇数,要么全为偶数所需消耗的最少能量。

样例输入

3
1 2 3

样例输出

3

数据范围

题解

最优情况是取 ,然后分别计算变成全偶数和全奇数的情况即可,

参考代码

  • Python
# 读取输入
n = int(input())
books = list(map(int, input().split()))

# 初始化变成全奇数和全偶数的代价
cost_to_odd = 0
cost_to_even = 0

# 遍历每本书,计算代价
for book in books:
    if book % 2 == 0:  # 如果是偶数
        cost_to_odd += book + 1  # 变成奇数的代价
    else:  # 如果是奇数
        cost_to_even += book + 1  # 变成偶数的代价

# 输出较小的代价
print(min(cost_to_odd, cost_to_even))
  • Java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取书的数量
        int n = scanner.nextInt();
        
        // 初始化变成全奇数和全偶数的代价
        long costToOdd = 0;
        long costToEven = 0;
        
        // 遍历每本书,计算代价
        for (int i = 0; i < n; i++) {
            int book = scanner.nextInt();
            if (book % 2 == 0) {  // 如果是偶数
                costToOdd += book + 1;  // 变成奇数的代价
            } else {  // 如果是奇数
                costToEven += book + 1;  // 变成偶数的代价
            }
        }
        
        // 输出较小的代价
        System.out.println(Math.min(costToOdd, costToEven));
        
        scanner.close();
    }
}
  • Cpp
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    // 初始化变成全奇数和全偶数的代价
    long long cost_to_odd = 0, cost_to_even = 0;
    
    // 遍历每本书,计算代价
    for (int i = 0; i < n; i++) {
        int book;
        cin >> book;
        if (book % 2 == 0) {  // 如果是偶数
            cost_to_odd += book + 1;  // 变成奇数的代价
        } else {  // 如果是奇数
            cost_to_even += book + 1;  // 变成偶数的代价
        }
    }
    
    // 输出较小的代价
    cout << min(cost_to_odd, cost_to_even) << "\n";
    
    return 0;
}

02.LYA的魔法树园

问题描述

LYA 是一位热爱魔法的少女。她的魔法树园里有许多奇妙的树,每棵树都有一个根节点和若干子节点。LYA 发现,当两个节点拥有相同数量的直接子节点时,这两个节点就

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

学长刷题笔记 文章被收录于专栏

这里收集了超全的刷题笔记,欢迎大家的订阅,会持续跟新的

全部评论
漏了两道题
点赞 回复 分享
发布于 09-07 14:28 安徽
美团今天算法岗笔试会更新吗
点赞 回复 分享
发布于 09-07 15:17 北京
LYA的魔法树园好像有个很坑的点,输入边的时候不是按照父子顺序输入的
点赞 回复 分享
发布于 09-07 18:42 安徽

相关推荐

1 4 评论
分享
牛客网
牛客企业服务