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

第四次作业

7-3 选点问题
数轴上有n个闭区间[ai, bi]。取尽量少的点,使得每个区间内都至少有一个点(不同区间内含的点可以是同一个)。
我的贪心策略:
在对区间的开始进行升序排序后,当区间存在重叠时,即区间的开始小于我的结束标准(eend)时,就可以仅取一个点来代表这两个区间。对于这个结束标准(eend),是每一次进行区间比较时确定的,它是出现区间重叠现象时,取两个区间bi更小的那一个bi作为结束标准,否则就以当前区间的结束作为eend,关键代码如下:
if(q[j].start<=eend){
eend=min(eend,q[j].end);
}
else{
dot++;
eend=q[j].end;
}
其中q是存储n个区间的结构体,dot是点的数量。
贪心选择性质:算法对于点的位置的选择后,剩余问题形式相同且独立,同时,每一步都导向整体最优解。
时间复杂度:在贪心选择方面,只需做n次循环,因此时间复杂度是O(n)。
贪心算法相较于动态规划算法来说是从上而下的,它的时间复杂度通常较低,算法也较为容易理解,但不一定能保证得到全局最优解。

http://www.gsyq.cn/news/73430.html

相关文章:

  • 2025年12月广东佛山青瓦/琉璃瓦制造厂家排行榜前十名:专业评测与选购指南
  • Kaplay
  • 2025初中培训机构精选推荐:初三冲刺封闭式全托辅导机构|一对一的初中辅导机构推荐
  • 最好的美白丸怎么选?跨国临床数据对照后的真实排名
  • ZZ1061. [ABC110D] Factorization
  • 2025年12月武汉律师推荐:五强实力与口碑对比评测
  • Ancora GaN driver circuit
  • 2025汽车脚垫五大品牌权威推荐:深度测评指南,卡骐盾TPE
  • 2025年五大留学机构排行榜,优越留学对小众专业有经验吗?优
  • 2025年GEO优化实力厂家排行榜,谁主沉浮?GEO优化服务/GEO优化AI工具排名/广告全案策划、制作、发布GEO优化品牌哪家好
  • 手写8000行代码构建完整AI训练推理流水线
  • 2025年柔性夹爪选型指南:如何选择可靠的夹爪厂家
  • Visual Studio 2026 Product Keys
  • 计算粗心马虎纠正初中数学辅导精选:从根源培养严谨习惯,有效减少不必要的失分
  • 2025年上海AI搜索结果优化渠道权威推荐榜单:上海AISEO机构/上海GEO关键词优化代运营/上海AI结果优化营销服务商综合评测
  • CAP博客集合
  • 【SPIE出版 | EI检索】第七届光电材料与器件国际研讨会(ICOMD 2025)
  • 2025年智能传感器五大品牌推荐榜单,看哪家口碑好
  • 2025年Q4顶尖内容审核公司推荐:AI驱动合规时代的全场景防护指南
  • 年度绩效考核推进需要注意的五大事项
  • 2025年N2氮气发泡罐批发厂家权威推荐榜单:鞋底中底发泡罐/体育器材发泡罐/高压发泡罐源头厂家精选
  • 服务好的大型工厂车间降温工业冷风机公司,车间厂房工厂通风降温/铁皮车间降温/陶瓷车间降温/炼钢车间通风降温工业冷风机公司排行榜
  • 2025年不锈钢压滤机厂家权威推荐榜单:聚焦技术实力与行业适配力
  • 2025年炔二醇润湿剂订制厂家权威推荐榜单:非硅润湿剂/润湿剂订做/非离子型润湿剂源头厂家精选
  • 2025 年B2B海外社媒营销公司深度推荐:涵盖海外短视频营销、海外社媒运营推广公司(2025年12月新版)
  • 2025年工业清洗机十大品牌推荐:工业清洗机哪家好
  • 基于STM32的多路LED频闪系统设计与实现
  • 《ESP32-S3使用指南—IDF版 V1.6》第五十三章 TCPClient实验
  • 2026 年广东 PET/KET 培塑之路,五大机构的实力隐线与择课指南
  • QtMainWindow C++详解:构建桌面应用的核心框架 - 教程