Codeforces Round #717 Baby Ehab Partitions Again

题意

给你一个长度为$n$的数组$a$。定义美的数组：如果这个数组分成两组，存在一种分法，使得两组的和相同。问：最少移除多少个数，使得这个数组不美。

定义$sum=\sum_{i=1}^n a_i$。如果$sum$是一个奇数，那么显然不需要移除。

如果$sum$是偶数，那么我们跑一个容量为$\frac {sum}2$的01背包，如果不存在解，那么也不需要移除。

于是到此，原数组$a$，一定需要移除点什么。

首先，如果$a$中存在奇数，那么直接移除这个奇数，使得$sum$变成奇数。

如果不存在奇数，那就意味着$a$里面全是偶数咯。那么，在移除任何数之前，我们将整个数组除以2，仍然能沿用之前的分组方式使得两组和相等。

如果除以2之后出现了奇数，那么就移除这个奇数。如果除以2之后还是全都是偶数，那么就一直除，直到第一次出现奇数。