一堆木头棍子共有 �n 根每根棍子的长度和宽度都是已知的。棍子可以被一台机器一个接一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的:第一根棍子的准备时间为 11 分钟。如果刚处理完长度为 �l宽度为 �w 的棍子那么如果下一个棍子长度为 ��l i 宽度为 ��w i 并且满足 �≥��l≥l i 、�≥��w≥w i 这个棍子就不需要准备时间否则需要 11 分钟的准备时
思路:贪心算法
首先将所有棍子按照长度从小到大排序,如果长度相同则按照宽度从小到大排序。之后按照顺序加工每一根棍子,如果当前棍子的长度和宽度都大于等于上一根棍子,则不需要准备时间;否则需要准备时间。
具体实现时,我们可以定义一个变量 $last$ 表示上一根被加工的棍子,初始值为第一根棍子。然后对于每一根棍子 $i$,如果 $i$ 的长度和宽度都大于等于 $last$,则将 $last$ 更新为 $i$,否则将准备时间加 $1$ 并将 $last$ 更新为 $i$,表示需要准备时间。
最后返回准备时间即可。
代码:
原文地址: https://www.cveoy.top/t/topic/fbD0 著作权归作者所有。请勿转载和采集!