【备战秋招】拼多多25届秋招笔试真题第一套

✅ 秋招备战指南 ✅

💡 学习建议:

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

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

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

🌸 目前本专栏已经上线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]));
     

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

互联网刷题笔试宝典 文章被收录于专栏

互联网刷题笔试宝典,这里涵盖了市面上大部分的笔试题合集,希望助大家春秋招一臂之力

全部评论

相关推荐

评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务