CF808E 题解

很好的一道分类讨论题。

观察数据范围，\(w \leq 3\)，不难想到，将 \(w\) 分为 \(1,2,3\) 种情况，如果直接贪心选会不难发现是错的。但是如果 \(w\) 的值只有 \(2\) 种，就像 \(w=1/2\) 的情况，将 \(w=1/2\) 的数据按价值排序，最后枚举每种选多少即可。但是 \(w=3\) 就会显得难以处理，需要讨论将多少种 \(w=1/2\) 的商品取出，十分不简洁。

于是考虑贪心选 \(w=2/3\) 的，不难想到，可以将 \(w=1\) 的两个商品合成一个混进 \(w=2\) 的商品中，然后枚举两种商品各占的空间，取最大值即可。

值得注意的地方在于，如果 \(w=1\) 的商品个数为奇数，肯定会剩下一个，那么如果要选这一个的话必须让其价值最大。

求解过程中，计算价值为 \(O(1)\)，合并以及枚举空间都为 \(O(n)\)，排序为 \(O(n \log n)\)，所以总时间复杂度为 \(O(n \log n)\)，可以通过此题。