Codeforces Round #750 Luntik and Concerts 题解 (Java/C++)

题解

先说结论，结论是，如果总时间数是偶数则输出0，否则输出1。

首先我们考虑只有3分钟的歌的情况。这种情况的答案显然是0或者3。

接着由于每种歌至少一首，因此我们考虑只有2分钟和3分钟的歌的情况。此时结果的最大值是2。（我们后面再来证明这一点）

此时，我们再考虑1分钟的歌。我们基于前面只有2分钟的歌和3分钟的歌的情况，我们至少能把结果的最大值限制在0和1之间。而具体是0还是1，取决于把2分钟和3分钟的歌导致的差异抹去后，剩下的1到底是奇数还是偶数。

因此，最终结果就是看总和是不是偶数。

最后我们来证明只有2分钟的歌和只有3分钟的歌导致的差异最多是2这一点。
我们假设存结果为3的情况，然后我们来构造出一种方式，使其结果更小就可以证明上面的结论了。
首先，如果时间较长的一边中存在2分钟的歌，那么只需要移动一首2分钟的歌到另一边，立刻就可以得到1。
相反，如果时间较长的一边不存在2分钟的歌，那么时间较长的一边就必然全是3分钟的歌。那么另一边一定存在2分钟的歌，我们移动一首3分钟的歌去另外一边，就可以构造上一种情况。于是也能得到1。
因此不存在结果为3的情况。

代码

Java

C++