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

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

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

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

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

🍥 本次是 前缀和，差分 专场，对这两个不太熟的朋友这场有难了！

1️⃣ 比较简单的小学数学题，枚举抽月卡的次数就行

2️⃣ 在笔试中看到区间 +- 的题目就应该往 差分 或者 线段树/树状数组 上想准没错了

3️⃣ 前缀和+二分，难度中等，还是有一些细节的

🍧 01.LYA的抽卡策略

问题描述

LYA是一款热门手机游戏的忠实玩家。游戏中有一个限时抽卡活动，LYA想抽到自己心仪的角色。为此，她需要至少 个游戏币。

目前，LYA的账户中没有任何游戏币，而距离抽卡活动结束还有 天。

游戏币有两种获取方式：

1. 购买月卡：每张月卡售价 元，可以获得 天的每日福利。每天可以领取一次福利（ 游戏币），购买当天可额外获得 游戏币。

2. 直接购买：每 元可以购买 个游戏币。

LYA想要用最少的钱获得所需的游戏币。你能帮她计算出最小花费吗？

输入格式

输入一行，包含两个整数 和 ，分别表示LYA需要的最少游戏币数量和距离活动结束的天数。

输出格式

输出一个整数，表示LYA需要花费的最少金额（单位：元）。

样例输入

3200 35

样例输出

50

数据范围

题解

枚举购买月卡的次数

1. 遍历可能的月卡购买次数（0到 ）。
2. 对每种情况，计算通过月卡获得的游戏币数量。
3. 如果月卡获得的游戏币不足，计算需要直接购买的游戏币数量。
4. 计算总花费，并更新最小花费。

时间复杂度为 ，空间复杂度为 。注意处理边界情况和整数除法的向上取整。

参考代码

• Python

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

# 初始化最小花费为一个很大的数
min_cost = float('inf')

# 枚举购买月卡的次数
for i in range((m + 29) // 30 + 1):
    # 计算通过月卡获得的游戏币
    coins_from_cards = 300 * i + min(m, i * 30) * 90
    
    # 计算还需要直接购买的游戏币数量
    coins_to_buy = max(0, n - coins_from_cards)
    
    # 计算总花费
    total_cost = i * 30 + (coins_to_buy + 9) // 10
    
    # 更新最小花费
    min_cost = min(min_cost, total_cost)

# 输出结果
print(min_cost)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        
        // 初始化最小花费为一个很大的数
        int minCost = Integer.MAX_VALUE;
        
        // 枚举购买月卡的次数
        for (int i = 0; i <= (m + 29) / 30; i++) {
            // 计算通过月卡获得的游戏币
            int coinsFromCards = 300 * i + Math.min(m, i * 30) * 90;
            
            // 计算还需要直接购买的游戏币数量
            int coinsToBuy = Math.max(0, n - coinsFromCards);
            
            // 计算总花费
            int totalCost = i * 30 + (coinsToBuy + 9) / 10;
            
            // 更新最小花费
            minCost = Math.min(minCost, totalCost);
        }
        
        // 输出结果
        System.out.println(minCost);
    }
}

• Cpp

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    // 初始化最小花费为一个很大的数
    int min_cost = 1e6;
    
    // 枚举购买月卡的次数
    for (int i = 0; ; i++) {
        if (i > (m + 29) / 30) break;
        
        // 计算通过月卡获得的游戏币和需要直接购买的游戏币
        int coins_from_cards = 300 * i + min(m, i * 30) * 90;
        int coins_to_buy = max(0, n - coins_from_cards);
        
        // 计算总花费并更新最小花费
        int total_cost = i * 30 + (coins_to_buy + 9) / 10;
        min_cost = min(min_cost, total_cost);
    }
    
    // 输出结果
    cout << min_cost << "\n";
    return 0;
}

🫐 02.园艺大师的难题

问题描述

LYA 是一位著名的园艺大师，她接到了一个特别的任务：在一条长度为 米的花园小径上种植树木。她雇佣了 名园丁来完成这项工作。每位园丁负责在一段特定的区间 内种树，其中 和 分别表示该园丁负责的起始和结束位置（以米为单位）。

然而，由于每个位置最多只能种一棵树，如果某个园丁发现自己要种树的位置已经有树了，他就会跳过这个位置。LYA 为了控制成本，想要恰好解雇一名园丁，但她不希望这会影响最终的种树结果。

现在，LYA 需要你的帮助来计算有多少名园丁可以被解雇，而不会影响最终的种树结果。

输入格式

第一行输入两个整数 和 （，），分别表示花园小径的长度和园丁的数量。

接下来的 行，每行输入两个正整数 和 （），表示第 位园丁负责种树的区间。

输出格式

输出一个整数，表示可以被解雇的园丁数量。

样例输入

5 3
1 4
1 2
3 4

样例输出

3

样例解释

每个园丁都可以被解雇

数据范围

题解

本题的核心思路是使用差分数组和前缀和来统计每个位置的树木数量。

只有当园丁负责的区间内所有树木都是有其他园丁种植时，该园丁才可以被解雇。

1. 使用差分数组记录每个园丁的种树区间。
2. 计算前缀和，得到每个位置的树木数量。
3. 对每个园丁，检查其负责区间内是否有唯一的树木。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

# 差分数组，用于记录每个位置的树木数量变化
d = [0] * (n + 2)
# 存储每个园丁负责的区间
v = []

# 读取输入并处理
for _ in range(m):
    l, r = map(int, input().split())
    v.append((l, r))
    # 差分数组操作：区间起点 +1，终点后一位 -1
    d[l] += 1
    d[r + 1] -= 1

# 前缀和数组，用于记录每个位置实际种植的树木数量
s = [0] * (n + 1)
for i in range(1, n + 1):
    s[i] = s[i - 1]
    # 计算差分数组的前缀和
    d[i] += d[i - 1]
    # 如果当前位置只有一棵树，记录在前缀和数组中
    if d[i] == 1:
        s[i] += 1

res = 0
# 检查每个园丁是否可以被解雇
for l, r in v:
    # 如果园丁负责的区间内没有唯一的树，则可以被解雇
    if s[r] - s[l - 1] == 0:
        res += 1

# 输出结果
print(res)

• Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        
        // 差分数组，用于记录每个位置的树木数量变化
        int[] d = new int[n + 2];
        // 存储每个园丁负责的区间
        int[][] v = new int[m][2];
        
        // 读取输入并处理
        for (int i = 0; i < m; i++) {
            input = br.readLine().split(" ");
            int l = Integer.parseInt(input[0]);
            int r = Integer.parseInt(input[1]);
            v[i][0] = l;
            v[i][1] = r;
            // 差分数组操作：区间起点 +1，终点后一位 -1
            d[l] += 1;
            d[r + 1] -= 1;
        }
        
        // 前缀和数组，用于记录每个位置实际种植的树木数量
        int[] s = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1];
            // 计算差分数组的前缀和
            d[i] += d[i - 1];
            // 如果当前位置只有一棵树，记录在前缀和数组中
            if (d[i] == 1)
                s[i]++;
        }
        
        int res = 0;
        //