✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

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

🌸 目前本专栏已经上线90+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

题目一：小基的环球美食之旅

1️⃣：将城市按优先级排序，从高到低依次访问

2️⃣：计算每个城市的最早可访问时间，考虑城市可访问时间和等待周期

3️⃣：贪心选择最早可访问的时间点

难度：中等

这道题目的核心是贪心算法。由于必须按照优先级顺序访问城市，我们需要找到每个城市在满足前序访问条件下的最早可能访问时间。题目的关键在于理解城市的可访问时间规则，并正确计算在已过去一定天数后的下一个可访问时间点。

题目二：小基的任务管理系统

1️⃣：使用优先队列维护可处理的任务，按所需时间排序

2️⃣：优先处理所需时间短的任务，减少总等待时间

3️⃣：处理任务时考虑任务创建时间和当前时刻的关系

难度：中等偏难

这道题目结合了贪心思想和优先队列操作。关键在于理解任务的调度规则：同一时刻只能处理一个任务，且任务可以暂停和恢复。通过优先处理所需时间短的任务，可以最小化所有任务的完成时间之和。

题目三：花园美化计划

1️⃣：将红玫瑰视为-1，白牡丹视为1，计算数组总和

2️⃣：使用动态规划找出所有可能的子数组和

3️⃣：应用公式计算所有可能的和谐度值

难度：中等

这道题目通过巧妙的问题转化，将花园美化问题转换为子数组和问题。关键洞察是：替换一个区间等效于将该区间内的数值取反，对总和的影响是减去两倍的区间和。使用动态规划可以高效找出所有可能的子数组和，从而计算出所有可能的和谐度。

题目四：图书馆整理系统

1️⃣：构建有向图表示书籍间的放置依赖关系

2️⃣：计算每本书的入度，处理放置冲突

3️⃣：使用优先队列进行拓扑排序，获取字典序最小的结果

难度：高

这道题目需要将书籍放置问题建模为图论问题，使用拓扑排序求解。关键是理解书籍之间的依赖关系：如果一本书占据了另一本书的理想位置，则前者必须在后者之前放置。通过小根堆实现的拓扑排序可以保证获得字典序最小的结果。

01. 小基的环球美食之旅

问题描述

小基 是一位美食博主，她计划进行一次环球美食之旅。她列出了 个世界知名的美食城市，每个城市都有其独特的美食文化。为了确保旅程的顺畅，小基 为每个城市设定了一个品尝优先级，数字越小表示优先级越高，她必须按照优先级从高到低的顺序访问这些城市。

然而，由于各个城市的美食节日和当地活动的限制，小基 只能在预定的第 天到达城市 。如果错过了这一天，她就需要等待 天才能再次品尝该城市的美食。也就是说，小基 只能在第 , , , ... 天到达城市 。

小基 想知道她至少需要多少天才能完成这次环球美食之旅，品尝到所有城市的美食。

输入格式

第一行包含一个整数 ，表示 小基 计划访问的城市数量。

接下来的 行，每行包含三个整数 、 和 ，分别表示：

• ：城市 的美食品尝优先级
• ：城市 的初次可访问时间
• ：错过后需要等待的天数

输出格式

输出一个整数，表示 小基 完成环球美食之旅所需的最少天数。

样例输入

2
1 2 2
2 1 3

样例输出

4

样例	解释说明
样例1	对于样例输入：

• 城市1的优先级最高（），初次可访问时间是第2天（）。
• 城市2的优先级次之（），初次可访问时间是第1天（）。

小基的行程安排如下：

1. 第2天访问城市1（优先级最高）。
2. 第4天访问城市2（因为错过了第1天，所以要等到第4天 ）。 |

数据范围

• 
• 
• 

题解

这道题目的核心是贪心算法。我们需要按照优先级顺序访问城市，同时选择最早的可能访问时间。

考虑题目条件：城市必须按照优先级从高到低访问，而每个城市只能在特定的日期访问。我们可以这样思考：

1. 首先，将所有城市按照优先级 从小到大排序。
2. 从最高优先级的城市开始，依次安排访问时间。
3. 对于每个城市，我们需要找到满足以下条件的最早可访问时间：
   • 不早于当前已经过去的天数
   • 符合城市的可访问日期规则（）

让我们举个例子来理解：假设当前已经过去10天，而某个城市的初次可访问时间是第3天，等待周期是5天。那么，这个城市的可访问时间点是3, 8, 13, 18...等。由于已经过去10天，所以最早可以在第13天访问该城市。

具体算法步骤如下：

1. 排序城市按优先级
2. 维护一个当前天数 curr_day，初始为0
3. 遍历排序后的城市列表：
   • 如果 curr_day < X_i，直接将 curr_day 更新为 X_i
   • 否则，计算下一个可访问时间：X_i + ceil((curr_day - X_i) / D_i) * D_i
   • 更新 curr_day 为计算出的访问时间

这种方法的时间复杂度是 ，主要来自于排序操作。空间复杂度是 ，用于存储城市信息。对于题目给出的数据范围（），这个算法是高效的。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

def min_days(n, cities):
    # 按优先级排序
    cities.sort(key=lambda x: x[0])
    
    day = 0
    for p, x, d in cities:
        # 找到最早可访问日期
        if day < x:
            day = x
        else:
            # 计算下一个可访问日期
            day = x + ((day - x + d - 1) // d) * d
    
    return day

def main():
    n = int(input())
    cities = []
    for _ in range(n):
        p, x, d = map(int, input().split())
        cities.append((p, x, d))
    
    print(min_days(n, cities))

if __name__ == "__main__":
    main()

• Cpp

#include 
#include 
#include 
using namespace std;

struct City {
    int p, x, d;
};

bool cmp(const City &a, const City &b) {
    return a.p < b.p;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector cities(n);
    for (int i = 0; i < n; i++) {
        cin >> cities[i].p >> cities[i].x >> cities[i].d;
    }
    
    // 按优先级排序
    sort(cities.begin(), cities.end(), cmp);
    
    int day = 0;
    for (auto &city : cities) {
        if (day < city.x) {
            day = city.x;
        } else {
            // 计算下一个可访问日期
            day = city.x + ((day - city.x + city.d - 1) / city.d) * city.d;
        }
    }
    
    cout << day << endl;
    return 0;
}

• Java

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

public class Main {
    static class City {
        int p, x, d;
        
        City(int p, int x, int d) {
            this.p = p;
            this.x = x;
            this.d = d;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        List cities = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String[] parts = br.readLine().split(" ");
            int p = Integer.parseInt(parts[0]);
            int x = Integer.parseInt(parts[1]);
            int d = Integer.parseInt(parts[2]);
            cities.add(new City(p, x, d));
        }
        
        // 按优先级排序
        Collections.sort(cities, (a, b) -> Integer.compare(a.p, b.p));
        
        int day = 0;
        for (City city : cities) {
            if (day < city.x) {
                day = city.x;
            } else {
                // 计算下一个可访问日期
                day = city.x + ((day - city.x + city.d - 1) / city.d) * city.d;
            }
        }
        
        System.out.println(day);
    }
}

02. 小基的任务管理系统

问题描述

小基 是一家科技公司的项目经理，她负责管理多个并行项目。公司最近开发了一个新的任务管理系统，可以帮助 小基 更高效地分配和完成任务。

系统有以下特点：

1. 同一时刻只能处理一个任务。
2. 任务可以在任意时刻开始、暂停和恢复（前提是该任务已开始且未完成）。
3. 每个任务有两个关键属性：所需时间 和创建时间 。
4. 任务的完成时间计算方式为：最后完成时刻减去任务创建时间 。

小基 希望能够最优化任务处理顺序，使得所有任务的完成时间之和最小。你能帮助她设计一个算法来实现这个目标吗？

输入格式

第一行包含一个整数 ，表示任务的总数。

接下来的 行，每行包含两个整数 和 ，分别表示第 个任务的所需时间和创建时间。

输出格式

输出一个整数，表示所有任务的最小完成时间之和。

样例输入

3
1 5
5 1
7 3

样例输出

10

样例	解释说明
样例1	有两种可能的处理方式：

方式一：

• 在时刻1到2处理任务1，完成时间为6-5=1
• 时刻6到7处理任务2，完成时间为7-1=6
• 时刻7到10处理任务3，完成时间为10-3=7 总完成时间和为1+6+3=10

方式二：

• 时刻1到5处理任务1
• 时刻5到6处理任务2，完成时间为6-5=1
• 时刻6到7完成任务1，完成时间为7-1=6
• 时刻7到10处理任务3，完成时间为10-3=7 总完成时间和为1+6+3=10

两种方式的结果相同，都是最优解。 | | 样例2 | 数据：

5
1 1
4 2
9 3
15 4
25 5

每个任务都可以在创建后立即开始处理，无需等待。因此总的完成时间和为1+2+3+4+5=15。 |

数据范围

• ；
• ；
• 数据保证对于任意 ，都有 。

题解

这道题目可以通过贪心算法和优先队列来解决。

首先，让我们理解题目的核心：我们需要安排任务的处理顺序，使得所有任务的完成时间之和最小。每个任务有两个属性：所需时间和创建时间。完成时间是指从创建时间开始到最终完成的时间跨度。

思路分析： 一个直观的想法是，应该优先处理那些所需时间较短的任务，这样可以尽快完成，减少整体等待时间。但我们还需要考虑任务的创建时间。

关键观察：如果两个任务都已经可以开始（即当前时间已经超过它们的创建时间），那么先处理所需时间较短的任务总是更优的。这是因为这样可以让两个任务的总完成时间更小。

算法步骤：

1. 按照任务所需时间 从小到大排序（题目已保证数据是排好序的）。
2. 维护一个当前时间 curr_time，初始为0。
3. 使用一个优先队列来存储已经可以开始但尚未完成的任务，按所需时间升序排列。
4. 遍历排序后的任务列表：
   • 处理优先队列中的任务，直到队列为空或当前时间不足以完成下一个任务。
   • 如果当前时间小于任务的创建时间，更新当前时间。
   • 将当前任务加入优先队列。
5. 处理队列中剩余的任务。

时间复杂度分析：

• 排序需要 的时间。
• 每个任务最多入队和出队一次，每次操作需要 的时间。
• 总的时间复杂度为 。

空间复杂度：

• 需要 的空间来存储任务和优先队列。

这个算法能够高效地处理题目中的数据范围（），是一个可行的解决方案。

参考代码

• Python

import sys
import heapq
input = lambda: sys.stdin.readline().strip()

def solve():
    n = int(input())
    curr = 0  # 当前时间
    ans = 0   # 总完成时间
    pq = []   # 优先队列
    
    for _ in range(n):
        t, w = map(int, input().split())
        
        # 处理队列中的任务
        while pq:
            time, create = pq[0]
            if t - curr >= time:
                # 能完成当前任务
                curr += time
                ans += curr - create
                heapq.heappop(pq)
            else:
                # 部分完成当前任务
                heapq.heappop(pq)
                time -= (t - curr)
                curr = t
                heapq.heappush(pq, (time, create))
                break
        
        # 更新当前时间
        if curr < t:
            curr = t
        # 加入新任务
        heapq.heappush(pq, (w, t))
    
    # 处理剩余任务
    while pq:
        time, create = heapq.heappop(pq)
        curr += time
        ans += curr - create
    
    return ans

print(solve())

• Cpp

#include 
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    ll curr = 0, ans = 0;
    // 小根堆，按所需时间排序
    priority_queue, vector>, greater<>> pq;
    
    for (int i = 0; i < n; i++) {
        ll t, w;
        cin >> t >> w;
        
        // 处理队列中的任务
        while (!pq.empty()) {
            auto [time, cr] = pq.top();
            if (t - curr >= time) {
                // 能完成当前任务
                curr += time;
                ans += curr - cr;
                pq.pop();
            } else {
                // 部分完成当前任务
                pq.pop();
                time -= (t - curr);
                curr = t;
                pq.push({time, cr});
                break;
            }
        }
        
        // 更新当前时间
        if (curr < t) curr = t;
        // 加入新任务
        pq.push({w, t});
    }
    
    // 处理剩余任务
    while (!pq.empty()) {
        auto [time, cr] = pq.top();
        pq.pop();
        curr += time;
        ans += curr - cr;
    }
    
    cout << ans << endl;
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        long curr = 0, ans = 0;
        // 小根堆，按所需时间排序
        PriorityQueue pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));