[POJ3614]Sunscreen[贪心]

题面

贪心策略: 奶牛按照minSPF降序排序, 对于每只奶牛尽量选符合要求且SPF大的防晒霜, 若没有符合要求的防晒霜就去除这只牛.

证明: 由于每头参加晒太阳的牛都要涂防晒霜, 所以我们要多用防晒霜. 按minSPF降序排序后, 对于某一头牛用哪一瓶防晒霜的决策, 这头牛可以选SPF大的或SPF小的防晒霜, 由于minSPF递减, 所以大的小防晒霜的都不会因为SPF太小而以后不能使用, 但可能因为SPF太大而不能被后面的牛使用, 所以能用大的防晒霜的时候要先把大的用出去. 另外, 每头牛对答案的贡献都是1, 因此不存在某头牛用不了防晒霜需要抢前面的防晒霜的情况, 也不存在某头牛用得了却要留给后面的牛的情况.

这种考虑当前决策范围拓展到后面对整体影响的方法叫做范围缩放.

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址