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

Solution:

Obviously, if two dishes are the same, then the total weight of the two dishes must also be the same. According to the previous question, we know that we can calculate the value range of the last remaining a. So the question is transformed into: For the dishes with the same remaining weight, according to the value range of a, how many different a are needed at least.

Assuming that the value ranges of $a_i$ and $a_j$ do not intersect, two different values must be required. Therefore, we only need to discretize the value range of a.
When an interval ends, we only need to apply the current value to all dishes in this interval. (because of a dish is not in this interval at this time, a new value is inevitably needed)

Code:

Java

C++