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

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

C++

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