【秋招笔试】8.11拼多多秋招第一场-三语言题解
🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试
💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 编程一对一辅导
✨ 本系列打算持续跟新
春秋招笔试题👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸
✨ 笔试合集传送们 -> 🧷春秋招笔试合集
🍒 本专栏已收集 50+套笔试题，
笔试真题会在第一时间跟新🍹 近期会进行一波价格调整，没订阅的朋友抓紧冲！！！
🌰 PDD秋招第一场，启动!!!
💡难难难！！！PDD的笔试难度从来没让人失望过
1️⃣ 第一题按照题意模拟，不是很难
2️⃣ 第二题是个用优先队列来优化的贪心问题。
3️⃣ 第三题是一道经典DP的变形题，但是比较难想。
4️⃣ 第四题比较困难，建图之后跑拓扑排序，但是边的数量可能非常大，要通过
100%的数据，需要上点数据结构的科技。
🍑 01.LYA的环球美食之旅
问题描述
LYA是一位美食博主，她计划进行一次环球美食之旅。她列出了 个世界知名的美食城市，每个城市都有其独特的美食文化。为了确保旅程的顺畅，LYA为每个城市设定了一个品尝优先级，数字越小表示优先级越高，她必须按照优先级从高到低的顺序访问这些城市。
然而，由于各个城市的美食节日和当地活动的限制，LYA只能在预定的第 天到达城市
。如果错过了这一天，她就需要等待
天才能再次品尝该城市的美食。也就是说，LYA只能在第
,
,
, ... 天到达城市
。
LYA想知道她至少需要多少天才能完成这次环球美食之旅，品尝到所有城市的美食。
输入格式
第一行包含一个整数 ，表示LYA计划访问的城市数量。
接下来的 行，每行包含三个整数
、
和
，分别表示：
：城市
的美食品尝优先级
：城市
：错过后需要等待的天数
输出格式
输出一个整数，表示LYA完成环球美食之旅所需的最少天数。
样例输入
2
1 2 2
2 1 3
样例输出
4
样例解释
对于样例输入：
- 城市1的优先级最高（
），初次可访问时间是第2天（
）。
- 城市2的优先级次之（
），初次可访问时间是第1天（
）。
LYA的行程安排如下：
- 第2天访问城市1（优先级最高）。
- 第4天访问城市2（因为错过了第1天，所以要等到第4天
）。
数据范围
题解
这道题目的核心思想是贪心算法。
我们需要按照优先级顺序访问每个城市，同时尽可能选择最早的可访问时间。
解题步骤如下：
-
首先，将所有城市按照优先级
-
初始化当前时间
current_day为0。 -
按优先级顺序遍历每个城市：
- 如果当前时间小于城市的初次可访问时间
- 如果当前时间大于
- 如果当前时间小于城市的初次可访问时间
-
更新当前时间为计算出的访问时间。
-
遍历完所有城市后，当前时间就是完成旅行所需的最少天数。
这种方法可以保证我们总是选择满足优先级要求的最早可能的访问时间，从而得到最优解。
参考代码
- Python
def min_days_for_food_tour(N, cities):
# 按优先级排序城市
cities.sort(key=lambda x: x[0])
current_day = 0
for _, X, D in cities:
# 找到最早可以访问该城市的日期
if current_day < X:
current_day = X
else:
# 计算下一个可访问的日期
current_day = X + ((current_day - X + D - 1) // D) * D
return current_day
# 处理输入
N = int(input())
cities = []
for _ in range(N):
P, X, D = map(int, input().split())
cities.append((P, X, D))
# 计算并输出结果
result = min_days_for_food_tour(N, cities)
print(result)
- Java
import java.util.*;
public class Main {
// 城市类,实现Comparable接口以便排序
static class City implements Comparable<City> {
int priority, firstVisit, interval;
City(int p, int x, int d) {
priority = p;
firstVisit = x;
interval = d;
}
@Override
public int compareTo(City other) {
return Integer.compare(this.priority, other.priority);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt(); // 读取城市数量
List<City> cities = new ArrayList<>();
// 读取每个城市的信息
for (int i = 0; i < N; i++) {
int P = scanner.nextInt(); // 优先级
int X = scanner.nextInt(); // 初次可访问时间
int D = scanner.nextInt(); // 等待间隔
cities.add(new City(P, X, D));
}
// 按优先级排序城市
Collections.sort(cities);
int currentDay = 0;
for (City city : cities) {
if (currentDay < city.firstVisit) {
currentDay = city.firstVisit;
} else {
// 计算下一个可访问的日期
currentDay = city.firstVisit +
((currentDay - city.firstVisit + city.interval - 1) / city.interval) * city.interval;
}
}
System.out.println(currentDay);
}
}
- Cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 城市结构体
struct City {
int priority, firstVisit, interval;
City(int p, int x, int d) : priority(p), firstVisit(x), interval(d) {}
};
// 比较函数,用于排序
bool compareCities(const City& a, const City& b) {
return a.priority < b.priority;
}
int minDaysForFoodTour(vector<City>& cities) {
// 按优先级排序城市
sort(cities.begin(), cities.end(), compareCities);
int currentDay = 0;
for (const auto& city : cities) {
if (currentDay < city.firstVisit) {
currentDay = city.firstVisit;
} else {
// 计算下一个可访问的日期
currentDay = city.firstVisit +
((currentDay - city.firstVisit + city.interval - 1) / city.interval) * city.interval;
}
}
return currentDay;
}
int main() {
int N;
cin >> N; // 读取城市数量
vector<City> cities;
for (int i = 0; i < N; i++) {
int P, X, D;
cin >> P >> X >> D; // 读取每个城市的信息
cities.emplace_back(P, X, D);
}
cout << minDaysForFoodTour(cities) << endl;
return 0;
}
🌈 02.LYA的任务管理系统
问题描述
LYA是一家科技公司的项目经理，她负责管理多个并行项目。公司最近开发了一个新的任务管理系统，可以帮助LYA更高效地分配和完成任务。
系统有以下特点：
- 同一时刻只能处理一个任务。
- 任务可以在任意时刻开始、暂停和恢复（前提是该任务已开始且未完成）。
- 每个任务有两个关键属性：所需时间
和创建时间
。
- 任务的完成时间计算方式为：最后完成时刻减去任务创建时间
LYA希望能够最优化任务处理顺序，使得所有任务的完成时间之和最小。你能帮助她设计一个算法来实现这个目标吗？
输入格式
第一行包含一个整数
，表示任务的总数。
接下来的 行，每行包含两个整数
和
，分别表示第
个任务的所需时间和创建时间。
输出格式
输出一个整数，表示所有任务的最小完成时间之和。
样例输入1
3
1 5
5 1
7 3
样例输出1
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
样例输出2
15
样例说明2
每个任务都可以在创建后立即开始处理，无需等待。因此总的完成时间和为1+2+3+4+5=15。
数据范围
；
；
- 数据保证对于任意
，都有
。
题解
这个问题可以通过贪心算法来解决。
核心思想是优先处理所需时间较短的任务，同时考虑任务的创建时间。
按照任务所需时间 从小到大排序。然后，使用一个优先队列来存储正在进行的任务，队列中的元素为
对。
遍历排序后的任务列表时，需要注意以下几点：
- 如果当前时间小于任务的创建时间，我们需要更新当前时间。
- 尝试完成优先队列中的任务，直到没有足够的时间或队列为空。
- 将当前任务加入优先队列。
这种方法确保了我们总是优先处理所需时间较短的任务，同时考虑了任务的创建时间，从而最小化总的完成时间。
参考代码
- Python
import heapq
def solve():
n = int(input())
fore = 0 # 当前时间
ans = 0 # 总完成时间
q = [] # 优先队列，存储任务
for _ in range(n):
t, w = map(int, input().split())
# 处理优先队列中的任务
while q:
nu, from_time = q[0]
if t - fore >= nu:
# 如果有足够的时间完成当前任务
fore += nu
ans += fore - from_time
heapq.heappop(q)
else:
# 如果时间不够，更新任务剩余时间并重新入队
heapq.heappop(q)
nu -= (t - fore)
fore = t
heapq.heappush(q, (nu, from_time))
break
# 更新当前时间
if fore < t:
fore = t
# 将新任务加入队列
heapq.heappush(q, (w, t))
# 处理剩余的任务
while q:
nu, from_time = heapq.heappop(q)
fore += nu
ans += fore - from_time
print(ans)
solve()
- 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));
int n = Integer.parseInt(br.readLine());
long fore = 0, ans = 0; // fore: 当前时间，ans: 总完成时间
// 使用优先队列存储任务，按照所需时间升序排列
PriorityQueue<long[]> q = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
for (int i = 1; i <= n; i++) {
String[] input = br.readLine().split(" ");
long t = Long.parseLong(input[0]);
long w = Long.parseLong(input[1]);
// 处理优先队列中的任务
while (!q.isEmpty()) {
long[] top = q.peek();
if (t - fore >= top[0]) {
// 如果有足够的时间完成当前任务
fore += top[0];
ans += fore - top[1];
q.poll();
} else {
// 如果时间不够，更新任务剩余时间并重新入队
q.poll();
top[0] -= (t - fore);
fore = t;
q.offer(top);
break;
}
}
// 更新当前时间
if (fore < t) fore = t;
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
这里收集了超全的刷题笔记，欢迎大家的订阅，会持续跟新的
