贪心算法求解邮差限时最大化投递信件数问题咨询

你的贪心策略选择和计算逻辑完全正确，邮差最终可投递的信件总数为10封。

• 贪心策略合理性：本题目标为1小时固定时长内最大化投递信件数，单封信件投递耗时随距离增加单调上升，因此优先选择投递距离最短、单封耗时最少的信件是适配本题目标的最优贪心策略，不存在策略选择错误。
• 单封耗时核算：按照给定公式t = 5 + 0.5log₃n计算各距离档位的单封投递耗时：
  • 距离为3时：log₃3=1，单封耗时5.5分钟
  • 距离为9时：log₃9=2，单封耗时6分钟
  • 距离为27时：log₃27=3，单封耗时6.5分钟
  • 距离为81时：log₃81=4，单封耗时7分钟
• 逐档投递耗时累计（总可用时长为60分钟）：
  1. 统计给定距离矩阵中，距离为3的信件共5封，全部投递累计耗时5*5.5=27.5分钟，剩余时长32.5分钟
  2. 距离为9的信件共3封，全部投递新增耗时3*6=18分钟，累计耗时45.5分钟，剩余时长14.5分钟
  3. 距离为27的信件共3封，单封耗时6.5分钟，最多可投递2封，新增耗时2*6.5=13分钟，累计耗时58.5分钟，剩余时长1.5分钟，不足以投递任何剩余信件（剩余1封27距离信件需6.5分钟、3封81距离信件单封需7分钟，均超出剩余时长）
• 总投递数核算：5+3+2=10封，和你的计算结果完全吻合。

注：你判断投递2封27距离信件的结论准确，若投递第3封27距离信件，总耗时会达到65分钟，超出1小时的时间限制，因此不能纳入投递集合。

内容的提问来源于stack exchange，提问作者Katerina