AcWing 110. 防晒

题目链接：110. 防晒 - AcWing题库

按照 minSPF 递减的顺序把奶牛排序，依次考虑每头奶牛。

对于每头奶牛，扫描一遍所有的防晒霜，在这头奶牛能用（指的是该防晒霜的强度符合这头奶牛的范围，并且瓶数还有剩余）的防晒霜里找 SPF 值最大的使用。

以上算法的贪心策略是在满足条件的前提下每次选 SPF 最大的防晒霜。

这个策略为什么是正确的呢？

我们考虑这一步策略的作用范围扩展到后续其他奶牛之后产生的影响。

每瓶防晒霜是否可用，会被 minSPF 与 maxSPF 两个条件限制。

因为奶牛已被按照 minSPF 递减排序，所以每一个不低于当前奶牛 minSPF 值的防晒霜，都不会低于后面其他奶牛的 minSPF。

也就是说，对于当前奶牛可用的任意两瓶防晒霜 $x$ 与 $y$，如果 SPF[$x$] $<$ SPF[$y$]，那么后面其他奶牛之可能出现 “$x, y$ 都能用” “$x, y$ 都不能用”“$x$ 能用，$y$不能用” 这三种情况之一。

因此，当前奶牛选择 maxSPF 较大的 $y$ 去使用，对于整体问题的影响显然比选择 maxSPF 较小的 $x$ 更好。

另外，每头奶牛对答案的贡献至多是 $1$。

即使让当前这头奶牛放弃日光浴，留下防晒霜给后面的某一头奶牛用，对答案的贡献也不会变得更大。

综上所述，尽量满足当前的奶牛，并选择 SPF 值尽量大的防晒霜是一个正确的贪心策略。

完整代码：防晒.cpp