Codeforces Round #753 Banquet Preparations 2 题解 (Java/C++)

题解

显然，如果两道菜一样，那么两道菜的总重量也一定一样。而根据上一道题目，我们知道我们是可以算出最后剩下的a的取值范围的。于是问题就转化成了：对于剩余重量相同的菜来说，根据a的取值范围，最少需要多少种不同的a。

假设$a_i$和$a_j$的取值范围不相交，那么必然需要两种不同的值。因此，我们只需要将a的取值范围离散化。
当一个区间结束的时候，因为如果此时某一道菜不在这个区间中，则不可避免的需要一个新的值，所以我们只需要把当前值应用到所有在这个区间中的菜即可。

Java

C++