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

题解

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

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

代码

Java

Submission #134370257 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #134370800 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论