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

题解

我们令每一道菜剩下来的总重量为$remain_i$，显然有$remain_i=a_i+b_i-m$。

于是为了尽可能的平衡a和b，显然我们的目标是$\sum a_i = \frac {\sum remain_i} 2$。
同时我们可以注意到，剩下的a的范围一定是在$[\min(remain_i, a_i), reman_i - \min(remain_i, b_i)]$。
因此，我们能得到$\sum a_i$的最大值和最小值。我们只需要根据$\sum a_i$和$\frac {\sum remain_i} 2$的差，调整每道菜剩下的a的数目即可。

代码

Java

C++