3 条题解
-
0
以下是为代码添加的完整注释,使用简单易懂的语言解释每一部分的功能,确保即使初学者也能理解:
include<cstdio> // 输入输出库(类似幼儿园的“说话工具”) include<algorithm> // 算法库(包含排序等工具) using namespace std; // 使用标准命名空间(避免重复写std::) // 定义任务结构体:每个任务有截止时间(t)和权重/收益(w) // 类似每个游戏任务有“最后完成时间”和“金币数量” struct node { int t; // 截止时间(比如第5天前必须完成) int w; // 权重/收益(完成任务的奖励金币数) a[1000100]; // 存放任务的数组(最多100万个任务) // 排序规则:按任务收益从大到小排序 // 就像把最贵的玩具排在前面 bool cmp(node x, node y) { return x.w > y.w; // 比较两个任务的金币数 bool b[1000100]; // 标记数组:记录每天是否被占用(true=已用,false=空闲) int l[1000100]; // 并查集数组:记录每个日期的“空闲位置” // 查找空闲日期的函数(核心!) // 作用:快速找到某个日期之前最近的空闲日期 int find(int x) { // 如果当前日期不是空闲(指向其他日期),就继续找它的“领导” if (l[x] != x) { l[x] = find(l[x]); // 路径压缩:直接让x指向最终的空闲日期 return l[x]; // 返回找到的空闲日期 int main() { int n, ans = 0; // n=任务数量, ans=总收益 scanf("%d", &n); // 输入任务数量 // 1. 读取每个任务的截止时间和收益 for (int i = 1; i <= n; i++) { scanf("%d %d", &a[i].t, &a[i].w); // 格式:截止时间 收益 // 2. 按收益从大到小排序(优先处理高收益任务) sort(a + 1, a + 1 + n, cmp); // 3. 初始化:每天都是空闲的,并指向自己 for (int i = 1; i <= n; i++) { l[i] = i; // 第i天空闲位置初始是第i天 // 4. 遍历所有任务(从收益最高的开始) for (int i = 1; i <= n; i++) { // 从截止时间往前找空闲日期 for (int j = a[i].t; j >= 1; j = l[j]) { // 关键:通过l[j]跳到前一个空闲日 if (!b[j]) { // 如果找到空闲日 b[j] = true; // 标记这天已被占用 l[j] = l[j] - 1; // 指向前一天(下次跳过已用日期) ans += a[i].w; // 累加当前任务的收益 break; // 找到位置后跳出循环 } // 更新截止时间的空闲位置(帮助后续任务快速查找) l[a[i].t] = find(a[i].t); printf("%d", ans); // 输出总收益 return 0;
🌟 核心原理通俗解释(幼儿园版): 任务排序:
把任务按金币数量从大到小排队,优先处理金币多的任务(类似先吃最甜的糖果)。 贪心策略:
每个任务尽量在截止时间完成。如果截止时间被占,就往前找空闲日(比如截止周五,就试周四、周三...)。 并查集优化:
l[] 数组像“跳跳杆”:遇到被占用的日期时,直接跳到前一个空闲日,避免重复检查[citation:7][citation:8]。
find() 函数像“找座位向导”:快速找到最近的空座位(空闲日期)[citation:6]。 收益累加:
只要任务找到空闲日完成,就把它的金币加入总收益 ans 中。
⚠️ 注意事项: 数组大小:代码预设数组大小为 1000100,若任务量超过此值需调整[citation:8]。
时间范围:截止时间不能超过数组最大下标(否则越界)。
适用场景:解决 带截止时间和收益的任务调度问题(如课程作业、工厂订单)[citation:8]。
举个例子:假设有3个任务:
任务A(截止第3天,收益50)
任务B(截止第2天,收益30)
任务C(截止第1天,收益20)
程序会先执行A(占第3天,收益+50),再执行B(占第2天,收益+30),最后C(占第1天,收益+20),总收益=100。
信息
- ID
- 614
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 12
- 已通过
- 2
- 上传者