25届-9.07团子改编题(研发岗)

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

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

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

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

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

alt

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

1️⃣ 简单的分奇偶考虑

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

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

📚 01.LYA的魔法书架

问题描述

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

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

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

输入格式

第一行一个整数 $n$ （ $1 \leq n \leq 10^5$ ），表示魔法书的数量。

第二行 $n$ 个整数，第 $i$ 个数为 $a_i$ （ $1 \leq a_i \leq 10^9$ ），表示第 $i$ 本书的魔力值。

输出格式

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

样例输入

3
1 2 3

样例输出

数据范围

$1 \leq n \leq 10^5$
$1 \leq a_i \leq 10^9$

题解

最优情况是取 $x = 1$ ，然后分别计算变成全偶数和全奇数的情况即可，

参考代码

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();
    }
}

#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;
}