POJ 3614 Sunscreen(贪心+优先队列)
Description
C头牛,L瓶防晒霜,
C行,每行代表每头牛既能日光浴又不会被晒伤时的spf取值范围
L行,每行代表每瓶防晒霜能使牛的spf值变成多少,以及每瓶能涂抹几头牛
求最多有几头牛可以既能晒日光浴又能不被晒伤
贪心
对牛和防晒霜从小到大排序
对于每瓶防晒霜来说,它有一个spf值,
找出所有下界小于spf的牛,放在一起
在这里面,上界也小于spf的牛可以直接扔掉(没救了)
上界大于spf即满足条件,此时防晒霜应优先给上界小的牛用
因为上界大的牛有更大的获得后续防晒霜的可能性
这里适合使用优先队列,从满足条件的牛中选出上界最小的
如果当前防晒霜用完了队列里还有牛,没关系,继续用下一瓶
Code
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66