博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
杭电OJ1789、南阳OJ236(贪心法)解题报告
阅读量:4663 次
发布时间:2019-06-09

本文共 825 字,大约阅读时间需要 2 分钟。

杭电OJ1789

南阳OJ236

1、最简单的贪心法是只有一个东西需要考虑(如安排会场,只需要将   "时间"  进行排序),

  即使需要考虑两个,也有一个明显的先后顺序(比如应先考虑开头时间,开头一样的,再找结束时间早的)

2、而稍难的问题如这两个题目的贪心法则是建立在两个处于平行地位的东西上进行的,(因为都需要同时考虑,如杭电OJ的时间与分数平等地位,南阳OJ的重量和长度地位平等)

  这个时候就需要对其中一个排序,对另一个通过for循环的形式进行遍历选择。

如杭电OJ中由于既要考虑期限大小,又要考虑分数高低,并且显然二者的地位是平等的,这时就需要先对其中一个进行排序,然后通过一个for循环进行遍历选择

具体操作为:首先将分数按大小排序,然后利用双层for循环(外层构造情景,也就是过程,内层进行遍历找到最优解)找到每个步骤的最优解

再具体一点就是:分数按照大小排序之后,先利用一个外层for来营造情景(也就是过程,本题为日期(第%d天)),然后利用内层for通过按顺序遍历排好序的数组找到最优解 

再如南阳OJ由于既要考虑木棒长度,又要考虑木棒的重量,并且二者的地位是相等的,这是也就需要先对其中一个进行排序,然后通过一个for循环进行遍历选择

具体操作是:首先将木棒长度排序,然后利用双层for循环(外层构造情景,也就是过程,内层进行遍历找到最优解)找到每个步骤的最优解

再具体一点就是:木棒按照长度排序之后,先利用一个外层for构造情景(也就是过程,本题为前一个木板的重量),然后利用内层for通过按顺序遍历排好序的数组找到最优解

概括一下就是先将其中一个变量 a 进行排序, 然后利用外层for与另一个变量b构造出过程,然后内层根据b 的最优进行遍历即可

(因为通过a的排序已经将化为最优,现在只需用循环找最优b即可)

 

转载于:https://www.cnblogs.com/MekakuCityActor/p/8228172.html

你可能感兴趣的文章
day3
查看>>
微信打开网页键盘弹起后页面会被顶上去,键盘收起,页面无法回到原来的位置,导致弹框里的按钮响应区域错位 position为fixed...
查看>>
没有世界末日的2012
查看>>
Check a dll is x64 or x86
查看>>
UWP 自定义控件:了解模板化控件 系列文章
查看>>
从源码看集合ArrayList
查看>>
mybatis配置多数据源(利用spring的AbstractRoutingDataSource)
查看>>
文章点击量排行TOP100-IBM power8算法挑战赛第三期
查看>>
前端常见问题
查看>>
熟悉常用的HDFS操作
查看>>
面向对象和面向过程的比较
查看>>
数据结构 树的建立与遍历
查看>>
[置顶] java swing的树操作(增删改)
查看>>
jetty对sessionId的处理分析
查看>>
代理的四种实现方式
查看>>
12-29 注册审核
查看>>
计算一个算数表达式的值
查看>>
hdu squarefree number
查看>>
atc-前端模板预编译器
查看>>
poj 3468 A Simple Problem with Integers 线段树区间加,区间查询和
查看>>