#P0036. 抢糖果
抢糖果
题目描述
小未和小来正在抢糖果。他们面前有一排 个糖果袋,第 个袋子里有 粒糖果。他们两个将按照第一个袋子到第 个袋子的顺序依次每轮拿取一个糖果袋。对于每个糖果袋的归属,他们有一个约定:如果一个袋子里的糖果数量是偶数,小未就抢走这袋糖果。否则则由小来拿去。
小未好胜心很强,所以他想重新排列这些糖果袋的顺序,这样在任何时刻(除了开始时两人都没有糖果),小未的糖果数都会严格多于小来。请帮助小未判断是否存在这样的重新排序可能。
输入格式
输入的第一行包含一个整数 ( ) - 测试用例的数量。
每个测试用例的第一行包含一个整数 ( ) - 糖果袋的数量。
每个测试用例的第二行包含 个空格分隔的整数 ( ) - 每个袋子中糖果的数量。
输出格式
对于每个测试用例,如果存在重新排序使得任何时刻(除了开始时两人都没有糖果),小未的糖果数都会严格多于小来,则输出 YES,否则输出 NO。
样例 #1
样例输入 #1
3
4
1 2 3 4
4
1 1 1 2
3
1 4 3
样例输出 #1
YES
NO
NO
样例 解释
在第一个测试用例中,小未可以对数组进行如下重新排序: .然后过程如下
- 第一个袋子中有 粒糖果,是偶数,所以小未拿走了它 - 小未有 粒糖果,小来有 粒糖果。
- 第二个袋子里有 颗糖果,是奇数,所以被小来拿走了--小未有 颗糖果,小来有 颗。
- 第三个袋子有 颗糖果,是偶数,所以小未拿走了它--小未有 颗糖果,而小来有 颗。
- 第四袋有 颗糖果,是奇数,所以由小来拿走--小未有 颗糖果,小来有 颗糖果。
由于小未的糖果数量总是比小来多,所以这种重新排序是有效的。