缘起
日常浪费生命 poj 3614 Sunscreen
分析
1 | 有C个奶牛去晒太阳 (1 <=C <= 2500),每个奶牛各自能够忍受的阳光强度有一个最小值和一个最大值,太大就晒伤 |
贪心策略还是想不到——QAQ,可耻的看了题解.
贪心策略如下
将牛按照_min升序排序, 然后将防晒霜按照spf升序排序. 例如牛排序为
1,2,3,4,5,6
防晒霜排序为
A,B,C,D
则对于A而言, 将_min<=A.spf的牛的_max值顺次入小根堆(这些可能领取A防晒霜). 堆的好处在于可以快速求最小,求什么的最小? 求_max的最小. 然后顺次考虑出堆的牛. 对于_max>=A.spf的牛可以领取防晒霜.然后A.num–
对于_max<A.spf或者A.num已经变为0时,牛是无法领取A防晒霜的. 注意,堆是小根堆. 即算法优先让_max较小的牛领取防晒霜. 这是符合直观的. 因为_max大的还有机会在A防晒霜消耗完毕之后,领取B防晒霜. 而_max小的就根本没机会领取B防晒霜了(因为防晒霜是按照spf升序排序的,既然小于A.spf,就更小于B.spf了)
然后再用此算法运行B. 注意,B中的小根堆可能有上一轮A剩下的_max>=B.spf>=A.spf 但是因为A防晒霜耗尽而没有领取到防晒霜的牛.
基于上述贪心思想+堆优化,不难写出如下代码
1 | //#include "stdafx.h" |
ac情况
Status | Accepted |
---|---|
Time | 16ms |
Memory | 148kB |
Length | 994 |
Lang | C++ |
Submitted | 2019-08-29 17:10:56 |
Shared | |
RemoteRunId | 20816034 |
Powered By Valine
v1.5.2
v1.5.2