【备战秋招】拼多多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天(
)。
小基的行程安排如下:
- 第2天访问城市1(优先级最高)。
- 第4天访问城市2(因为错过了第1天,所以要等到第4天
)。 |
数据范围
题解
这道题目的核心是贪心算法。我们需要按照优先级顺序访问城市,同时选择最早的可能访问时间。
考虑题目条件:城市必须按照优先级从高到低访问,而每个城市只能在特定的日期访问。我们可以这样思考:
- 首先,将所有城市按照优先级
从小到大排序。
- 从最高优先级的城市开始,依次安排访问时间。
- 对于每个城市,我们需要找到满足以下条件的最早可访问时间:
- 不早于当前已经过去的天数
- 符合城市的可访问日期规则(
)
让我们举个例子来理解:假设当前已经过去10天,而某个城市的初次可访问时间是第3天,等待周期是5天。那么,这个城市的可访问时间点是3, 8, 13, 18...等。由于已经过去10天,所以最早可以在第13天访问该城市。
具体算法步骤如下:
- 排序城市按优先级
- 维护一个当前天数
curr_day
,初始为0 - 遍历排序后的城市列表:
- 如果
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. 小基的任务管理系统
问题描述
小基 是一家科技公司的项目经理,她负责管理多个并行项目。公司最近开发了一个新的任务管理系统,可以帮助 小基 更高效地分配和完成任务。
系统有以下特点:
- 同一时刻只能处理一个任务。
- 任务可以在任意时刻开始、暂停和恢复(前提是该任务已开始且未完成)。
- 每个任务有两个关键属性:所需时间
和创建时间
。
- 任务的完成时间计算方式为:最后完成时刻减去任务创建时间
。
小基 希望能够最优化任务处理顺序,使得所有任务的完成时间之和最小。你能帮助她设计一个算法来实现这个目标吗?
输入格式
第一行包含一个整数
,表示任务的总数。
接下来的 行,每行包含两个整数
和
,分别表示第
个任务的所需时间和创建时间。
输出格式
输出一个整数,表示所有任务的最小完成时间之和。
样例输入
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。 |
数据范围
;
;
- 数据保证对于任意
,都有
。
题解
这道题目可以通过贪心算法和优先队列来解决。
首先,让我们理解题目的核心:我们需要安排任务的处理顺序,使得所有任务的完成时间之和最小。每个任务有两个属性:所需时间和创建时间。完成时间是指从创建时间开始到最终完成的时间跨度。
思路分析: 一个直观的想法是,应该优先处理那些所需时间较短的任务,这样可以尽快完成,减少整体等待时间。但我们还需要考虑任务的创建时间。
关键观察:如果两个任务都已经可以开始(即当前时间已经超过它们的创建时间),那么先处理所需时间较短的任务总是更优的。这是因为这样可以让两个任务的总完成时间更小。
算法步骤:
- 按照任务所需时间
从小到大排序(题目已保证数据是排好序的)。
- 维护一个当前时间
curr_time
,初始为0。 - 使用一个优先队列来存储已经可以开始但尚未完成的任务,按所需时间升序排列。
- 遍历排序后的任务列表:
- 处理优先队列中的任务,直到队列为空或当前时间不足以完成下一个任务。
- 如果当前时间小于任务的创建时间,更新当前时间。
- 将当前任务加入优先队列。
- 处理队列中剩余的任务。
时间复杂度分析:
- 排序需要
的时间。
- 每个任务最多入队和出队一次,每次操作需要
的时间。
- 总的时间复杂度为
。
空间复杂度:
- 需要
的空间来存储任务和优先队列。
这个算法能够高效地处理题目中的数据范围(),是一个可行的解决方案。
参考代码
- 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%内容,订阅专栏后可继续查看/也可单篇购买
互联网刷题笔试宝典,这里涵盖了市面上大部分的笔试题合集,希望助大家春秋招一臂之力