Solution:
Let me show the conclusion first. The conclusion is that if the total time is an even number, output 0, otherwise output 1.
First we consider the case that only have 3-minutes song. The answer in this case is obviously 0 or 3.
Then since there is at least one song for each kind of song, we consider the case of only 2-minutes songs and 3-minutes songs. The maximum value of the answer at this time is 2. (We will prove this later)
At this point, we consider 1-minute songs. Based on the previous situation that there are only 2-minutes songs and 3-minutes songs, we can at least limit the maximum value of the answer to between 0 and 1.
Whether the answer is 0 or 1 depends on whether the number of remaining 1s is odd or even after erasing the difference caused by the 2 minute and 3 minute songs.
Therefore, the answer is to see if the sum is even.
Finally, let us prove that the answer is 2 at most in case there are only 2-minutes songs and 3-minutes songs.
We assume that 3 is the answer, and then we construct a way to make the answer smaller to prove the above conclusion.
First, if there is a 2-minute song on the longer concerts, you only need to move a 2-minute song to the other side, and you will get 1 as answer immediately.
Conversely, if there are no 2-minute songs on the longer concert, then the longer concert must be all 3-minute songs. Then there must be a 2-minute song on the other concert. We move a 3-minute song to the other concert to construct the previous situation. Then you can get 1.
Therefore, there is no case where the answer is 3.
Code:
Java
C++
