当前位置: 首页 > news >正文

特地拎出来的总结

这篇总结不太一样,为了纪念和我爸喋喋不休吵了近3h的时间和教训,用Deepseek共同完成 :

题目

T674176 T2-任务task

题目描述

时间限制: 2.0 秒

空间限制: 512 MiB

\(n\) 个任务,第 \(i\) 个任务需要占据 \([l_i,r_i]\) 的时间,每个任务都会在瞬间结束,不会干扰到之后的任务。

你需要保证只使用 \(k\) 条并行线路完成任务,具体来说:

在选择任务后,你有 \(k\) 个流水线,第 \(t\) 流水线能分配若干任务 \([l_{t,i},r_{t,i}]\)
合法方案需要满足 \(l_{t,i+1}\ge r_{t,i}\),即结束时间不能超过下一个开始时间,且所有任务都分配进去。
也就是说:

  • 对于区间 \([1,2],[2,3]\),可以分配到一条流水线上;
  • 对于全部是 \([1,1]\) 区间的任务,都可以将其安排在一条流水线上;
  • 但是如果是 \([2,2]\)\([1,3]\) 两个区间就无法安排在一条流水线上。

输入格式

从标准输入读入数据。

第一行两个正整数 \(n,k\),表示任务的数量和同时最多能做的任务数。
接下来 \(n\) 行,第 \(i+1\) 行两个整数表示 \(l_i,r_i\)

输出格式

输出到标准输出。

输出一行一个整数,表示最多能完成的任务数。

输入输出样例 #1

输入 #1

3 1
1 2
2 3
1 3

输出 #1

2

说明/提示

补充样例0输入

3 1

1 1

1 1

1 1

样例0输出

3
样例1解释

做任务 \(1\) 和任务 \(2\)。注意任务 \(1\) 结束的那一刻不算正在做任务 \(1\),可以立即开始任务 \(2\)

对于所有的数据,1 ≤ k ≤n ≤ 10⁶, 0 ≤ lᵢ ≤ rᵢ ≤ n

子任务

测试点编号 \(n\leq\) 特殊性质
\(1\sim 3\) \(17\) \(k=1\)
\(4\sim 6\) \(17\) \(l_i\leq l_{i+1}\)\(r_i\leq r_{i+1}\)
\(7\sim 13\) \(17\) 无特殊性质
\(14\sim 16\) \(10^2\) \(k=1\)
\(17\sim 19\) \(10^2\) \(l_i\leq l_{i+1}\)\(r_i\leq r_{i+1}\)
\(20\sim 25\) \(10^2\) 无特殊性质
\(26\sim 28\) \(5\times 10^3\) \(k=1\)
\(29\sim 30\) \(5\times 10^3\) \(l_i\leq l_{i+1}\)\(r_i\leq r_{i+1}\)
\(31\sim 41\) \(5\times 10^3\) 无特殊性质
\(42\sim 43\) \(5\times 10^4\) \(k=1\)
\(44\sim 46\) \(5\times 10^4\) \(l_i\leq l_{i+1}\)\(r_i\leq r_{i+1}\)
\(47\sim 55\) \(5\times 10^4\) 无特殊性质
\(56\sim 58\) \(10^5\) \(k=1\)
\(59\sim 64\) \(10^5\) \(l_i\leq l_{i+1}\)\(r_i\leq r_{i+1}\)
\(65\sim 76\) \(10^5\) \(r_i-l_i<10\)
\(77\sim 83\) \(10^5\) 无特殊性质
\(84\sim 90\) \(10^6\) \(r_i-l_i<10\)
\(91\sim 92\) \(10^6\) \(k=1\)
\(93\sim 94\) \(10^6\) \(l_i\leq l_{i+1}\)\(r_i\leq r_{i+1}\)
\(95\sim 100\) \(10^6\) 无特殊性质

题目关键点

  • 问题本质:选择尽可能多的任务,使得在任何时刻最多有 ( k ) 个任务同时进行(任务在结束时刻不计入进行中)。
  • 核心约束:任务的时间区间 ([l_i, r_i]) 不能重叠超过 ( k ) 个,但允许任务在结束时刻立即开始下一个任务(即区间端点不重叠不计入冲突)。
  • 数据规模:( n \leq 10^6 ),需要高效算法。

正解思路

题解中提到的正确解决方案是:

  1. 排序策略:将任务按照结束时间 ( r_i ) 从早到晚排序。这有助于优先安排结束早的任务,为后续任务留出空间。
  2. 贪心选择:依次考虑每个任务,如果加入后不违反“任何时刻最多 ( k ) 个任务”的约束,则选择该任务。
  3. 约束检查:检查加入任务后,任务区间 ([l_i, r_i]) 内的同时任务数是否超过 ( k )。这需要动态维护每个时间点的任务数。
  4. 数据结构优化:使用线段树或堆来高效查询区间最大值和更新任务数。具体来说:
    • 线段树:维护时间轴上的任务数,支持区间查询最大值和区间加操作(当加入任务时,将 ([l_i, r_i]) 的任务数加1)。
    • 堆优化:由于只需要检查后缀最大值,可以用堆来维护当前进行中的任务结束时间,每次检查时弹出已结束的任务。

正解的时间复杂度为 ( O(n \log n) ) 或 ( O(n \log C) )(其中 ( C ) 是时间范围),能够处理 ( n \leq 10^6 ) 的数据。

做题情况分析

  • 暴力解法:最初实现了 ( O(n^2) ) 的暴力解法,即枚举任务组合并检查约束。这种方法在 ( n ) 较大时(如 ( n > 10^4 ))会超时,无法通过所有测试点。
  • 问题根源:对 ( k ) 的特殊性不敏感,没有意识到 ( k ) 可以作为优化关键。在暴力解法中,未能将问题转化为贪心选择与数据结构维护,导致无法优化到正解。
  • 具体不足
    • 没有使用排序策略来简化问题。
    • 没有利用数据结构高效检查区间任务数,而是每次重新计算,造成高复杂度。
    • 忽略了题解中提到的“结束时间排序”和“区间查询”的提示。

改进建议

  1. 转换思路:对于区间选择问题,优先考虑按结束时间排序的贪心策略,这常用于解决区间不重叠或资源限制问题。
  2. 利用 k 值:当 ( k ) 较小时,可以考虑更简单的优化;但即使 ( k ) 较大,也应使用数据结构维护全局约束。
  3. 掌握数据结构:熟练运用线段树、堆等数据结构处理区间查询和更新,这是解决大规模数据问题的关键。
  4. 代码实践:在实现正解时,注意离散化时间点以降低空间复杂度,并小心处理区间端点(如结束时刻不计入)。

通过本题,应加强贪心算法与数据结构的结合应用,避免陷入暴力枚举的思维定式。在类似问题中,及时分析约束条件并选择高效算法是得分的关键。

http://www.hskmm.com/?act=detail&tid=24419

相关文章:

  • 2025异型件厂家推荐:邯郸市烁燊紧固件,广泛应用于建筑、桥梁、机械、电力、交通等诸多领域
  • Allow or block media autoplay in Firefox
  • [WC2018] 即时战略
  • 实用指南:Unity学习之C#的反射机制
  • HDF5文件 ——之三
  • 代码随想录算法训练营|Day 25
  • 深入解析:SAE J3072-2024插电式电动汽车(PEV)中的车载逆变器系统安全标准介绍
  • 冷僻模板整理
  • 实用指南:gitlab-runner 再次实践中理解和学习
  • 2025年7月28日当周关键漏洞汇总分析
  • C# 与 C/C++ 互操作
  • 【自然语言处理】文本规范化知识点梳理与习题总结 - 教程
  • 邮票收集问题正推证明
  • 2025多校冲刺CSP模拟赛2 2025.10.4 模拟炸
  • 算法乱谈
  • 2025 年 9 月习题集
  • C# 代码规范
  • 实用指南:babelfish for postgresql 分析--todo
  • NFC 贴卡自动拨打微信视频电话
  • 10.4
  • 实用指南:d-分离:图模型中的条件独立性判定准则
  • [MCP] 监听资源更新
  • [RAG] 基础知识
  • CF1408F Two Different
  • 数据结构 - 字典树 Trie
  • 激活函数实现
  • 漏洞赏金入门指南:从零开始的实战方法论
  • PMON failed to acquire latch 的报错及sqlplus / as sysdba 无法连接 - 详解
  • 2025CSP-S模拟赛58 比赛总结
  • 精读C++设计模式20 —— 结构型设计模式:桥接模式 - 详解