给你一个长度为$n$的数组$a$.定义美的数组:如果这个数组分成两组,存在一种分法,使得两组的和相同.问:最少移除多少个数,使得这个数组不美.
如果$sum$是偶数,那么我们跑一个容量为$\frac {sum}2$的01背包,如果不存在解,那么也不需要移除.
于是到此,原数组$a$,一定需要移除点什么.
首先,如果$a$中存在奇数,那么直接移除这个奇数,使得$sum$变成奇数.
如果不存在奇数,那就意味着$a$里面全是偶数咯.那么,在移除任何数之前,我们将整个数组除以2,仍然能沿用之前的分组方式使得两组和相等.
如果除以2之后出现了奇数,那么就移除这个奇数.如果除以2之后还是全都是偶数,那么就一直除,直到第一次出现奇数.