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

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

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

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

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

🍥 本次代码的整体难度并不大，除了最后一题实现起来比较麻烦，其他三题应该都可以做

1️⃣ 简单的贪心+排序

2️⃣ 思维题，需要找到规律

3️⃣ 比较简单的树相关的题，DFS跑一遍就可以

4️⃣ 模拟+贪心，优先填入 2 x 2 的格子

💰 01.K小姐的购物策略

问题描述

K小姐是一位精明的购物爱好者。她有 张不同面额的购物卡，每张卡上都有一定金额。她发现一家商店正在进行一种特价商品的促销活动，每件特价商品的价格是 元。

K小姐计划每天使用一张购物卡购买尽可能多的特价商品，直到所有购物卡都无法再购买任何特价商品为止。在开始购物前，她可以向任意几张购物卡中充值，但总充值金额不能超过 元。

现在，K小姐想知道如果采用最优的充值策略，她最多能购买多少件特价商品。

输入格式

第一行包含三个整数 、 和 ，分别表示购物卡的数量、特价商品的单价和最大充值金额。

第二行包含 个整数 ，表示每张购物卡的初始金额。

输出格式

输出一个整数，表示K小姐最多能购买的特价商品数量。

样例输入

样例 1

5 3 2
4 4 3 1 2

样例 2

3 10 0
9 6 3

样例输出

样例 1

4

样例 2

0

数据范围

题解

排序

1. 首先，计算不进行充值时能购买的商品数量。这可以通过将每张购物卡的 金额除以商品单价 并取整来得到。

2. 对于 剩余的金额（每张卡的余额），需要考虑如何最有效地使用充值金额。最优策略是优先充值那些差额最小的购物卡，使其能够多购买一件商品。

3. 将购物卡按余额从大到小排序。这样可以优先考虑那些只需要少量充值就能多买一件商品的卡。

4. 遍历排序后的购物卡，如果充值金额足够使当前卡多买一件商品，就进行充值，并增加购买数量。

5. 最后，如果还有剩余的充值金额，可以直接用来购买商品。

参考代码

• Python

# 读取输入
n, k, m = map(int, input().split())
cards = list(map(int, input().split()))

# 计算初始可购买数量和余额
result = 0
remainders = []
for card in cards:
    result += card // k
    remainders.append(card % k)

# 对余额进行降序排序
remainders.sort(reverse=True)

# 遍历余额，进行充值
for remainder in remainders:
    if m >= k - remainder:
        result += 1
        m -= k - remainder
    else:
        break

# 使用剩余充值金额
result += m // k

# 输出结果
print(result)

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        long m = scanner.nextLong();
        
        long result = 0;
        List<Integer> remainders = new ArrayList<>();
        
        // 计算初始可购买数量和余额
        for (int i = 0; i < n; i++) {
            int card = scanner.nextInt();
            result += card / k;
            remainders.add(card % k);
        }
        
        // 对余额进行降序排序
        Collections.sort(remainders, Collections.reverseOrder());
        
        // 遍历余额，进行充值
        for (int remainder : remainders) {
            if (m >= k - remainder) {
                result++;
                m -= k - remainder;
            } else {
                break;
            }
        }
        
        // 使用剩余充值金额
        result += m / k;
        
        // 输出结果
        System.out.println(result);
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 读取输入
    long long n, k, m;
    cin >> n >> k >> m;
    
    long long result = 0;
    vector<int> remainders;
    
    // 计算初始可购买数量和余额
    for (int i = 0; i < n; i++) {
        long long card;
        cin >> card;
        result += card / k;
        remainders.push_back(card % k);
    }
    
    // 对余额进行降序排序
    sort(remainders.begin(), remainders.end(), greater<int>());
    
    // 遍历余额，进行充值
    for (int remainder : remainders) {
        if (m >= k - remainder) {
            result++;
            m -= k - remainder;
        } else {
            break;
        }
    }
    
    // 使用剩余充值金额
    result += m / k;
    
    // 输出结果
    cout << result << "\n";
    
    return 0;
}

🎵 02.LYA的魔法调音

问题描述

LYA是一位音乐魔法师，她有一个长度为 的音符序列。每个音符都有一个音高值，可能为正数、负数或零。LYA可以使用一种特殊的魔法：每次选择序列中的 个音符，将它们的音高值全部取反。LYA想知道，经过若干次魔法操作后，整个音符序列的音高值之和最大可以达到多少。

输入格式

第一行输入一个整数 ，表示魔法可以同时改变的音符数量。

第二行输入 个整数，表示音符序列中每个音符的音高值。

输出格式

输出一个整数，表示经过魔法操作后，音符序列的最大音高值之和。

样例输入

样例 1

3
-1 -2 3 -4 -5

样例输出

样例 1

15

数据范围

• 
• ，其中 表示每个音符的音高值

题解

思维题

如何 为偶数，且负数的个数为奇数个，则必然存在一个负数的情况。

其他情况均可变成所有都为正数

参考代码

• Python

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

# 记录负数的奇偶性并取绝对值
neg_count = 0
for i in range(len(arr)):
    if arr[i] < 0:
        neg_count ^= 1
        arr[i] = -arr[i]

# 计算总和
total = sum(arr)

# 处理特殊情况
if n % 2 == 0 and neg_count % 2 == 1:
    min_val = min(arr)
    total -= 2 * min_val

# 输出结果
print(total)

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        int[] arr = new int[2 * n - 1];
        
        // 记录负数的奇偶性并取绝对值
        boolean negCount = false;
        int minVal = Integer.MAX_VALUE;
        long total = 0;
        
        for (int i = 0; i < 2 * n - 1; i++) {
            arr[i] = scanner.nextInt();
            if (arr[i] < 0) {
                negCount = !negCount;
                arr[i] = -arr[i];
            }
            minVal = Math.min(minVal, arr[i]);
            total += arr[i];
        }
        
        // 处理特殊情况
        if (n % 2 == 0 && negCount) {
            total -= 2 * minVal;
        }
        
        // 输出结果
        System.out.println(total);
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 读取输入
    int n;
    cin >> n;
    vector<long long> arr(2 * n - 1);
    
    // 记录负数的奇偶性并取绝对值
    bool neg_count = false;
    for (auto& x : arr) {
        cin >> x;
        if (x < 0) {
            neg_count = !neg_count;
            x = -x;
        }
    }
    
    // 计算总和
    long long total = accumulate(arr.begin(), arr.end(), 0LL);
    
    // 处理特殊情况
    if (n % 2 == 0 && neg_count) {
        long long min_val = *min_element(arr.begin(), arr.end());
        total -= 2 * min_val;
    }
    
    // 输出结果
    cout << total << "\n";
    
    return 0;
}

🌲 03.奇妙树的修复

问题描述

LYA 是一位热爱园艺的少女，她最近在打理一棵特殊的树。这棵树有 个节点，每个节点都有一个魔力值 。LYA 发现，如果每个节点的魔力值都大于或等于其所有子节点的魔力值之和，这棵树就会散发出奇妙的光芒，她称之为"奇妙树"。

为了让这棵树变成奇妙树，LYA 可以对任意节点施加魔法，每次魔法可以使该节点的魔力值增加 1。LYA 想知道，最少需要施展多少次魔法，才能让这棵树变成奇妙树。

输入格式

第一行包含一个整数 ，表示树的节点数。

第二行包含 个整数 ，表示每个节点的初始魔力值。

接下来 行，每行包含两个整数 和 ，表示节点 和节点 之间存在一条边。

输出格式

输出一个整数，表示 LYA 最少需要施展的魔法次数。

样例输入

3
1 2 3
1 2
1 3

样例输出

4

数据范围

题解

贪心 + DFS

1. 理解奇妙树：在奇妙树中，每个节点的魔力值必须大于或等于其所有子节点的魔力值之和。我们需要从叶子节点开始，自底向上地调整魔力值。
2. 贪心策略：对于每个节点，只需要将其魔力值调整到刚好等于其子节点魔力值之和（如果原本就大于等于，则不需要调整）。这样可以保证使用最少的魔法次数。