#CF160A. 双胞胎
双胞胎
CF160A 双胞胎
题目描述
想象一下,你有一个双胞胎兄弟或姐妹。身边有一个长得和你一模一样的人,听起来确实挺神奇。至于拥有一个“另一个自己”究竟是好事还是坏事,还真不好说。不过,如果你真的有双胞胎,那你肯定深有体会。
现在,让我们设想一个你家里再普通不过的早晨。你还在呼呼大睡,妈妈却已经急着去上班了。她忙得团团转,差点忘了给自己最心爱的两个孩子留上午餐费,好让你们去学校食堂吃饭。她翻了翻钱包,找出了一些硬币,准确地说,是 枚价值分别为 的硬币。可妈妈实在赶时间,没来得及把硬币分给你们俩,只好潦草地写了张纸条,让你们平分这笔钱。
你醒来后,发现了妈妈留下的硬币和纸条。“为什么要平分呢?”——你这样想着。毕竟,双胞胎还在睡觉,什么都不会知道。于是你打算这么做:挑出一些硬币,使你拿到的硬币总价值严格大于剩下那些由双胞胎拿着的硬币总价值。不过,你也明白,拿太多硬币的话,双胞胎很可能会察觉不对劲。为了不引起怀疑,你决定采取如下策略:拿走总价值严格大于剩余硬币总价值的最少数量的硬币。请你求出,按照这种方式分配时,你至少需要拿走多少枚硬币。
输入格式
第一行输入一个整数 代表硬币的数量。
第二行输入 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 100\right)$ 代表每枚硬币的价值。所有数字之间用空格分隔。
输出格式
在一行上输出一个整数,代表所需拿走的最少硬币数量。
测试样例
2
3 3
2
样例 1 解释
你需要拿走 枚硬币,此时你和双胞胎手中的硬币总价值分别为 和 。如果只拿走 枚硬币,那么两边的总价值会分别是 和 ;如果一枚都不拿,两边的总价值则分别是 和 。这些方案都不符合要求,因为你的总价值必须严格大于双胞胎的总价值。
3
2 1 2
2
样例 2 解释
只拿一枚硬币同样不够。你可以拿价值为 的硬币,也可以拿价值为 的硬币。无论哪种情况,所需的最少硬币数量都是 。