160A. Twins

greedy, sortings, 900, https://codeforces.com/problemset/problem/160/A

Imagine that you have a twin brother or sister. Having another person that looks exactly like you seems very unusual. It's hard to say if having something of an alter ego is good or bad. And if you do have a twin, then you very well know what it's like.

Now let's imagine a typical morning in your family. You haven't woken up yet, and Mom is already going to work. She has been so hasty that she has nearly forgotten to leave the two of her darling children some money to buy lunches in the school cafeteria. She fished in the purse and found some number of coins, or to be exact, n coins of arbitrary values $a_{1}, a_{2}, . . ., a_{n}$ . But as Mom was running out of time, she didn't split the coins for you two. So she scribbled a note asking you to split the money equally.

As you woke up, you found Mom's coins and read her note. "But why split the money equally?" — you thought. After all, your twin is sleeping and he won't know anything. So you decided to act like that: pick for yourself some subset of coins so that the sum of values of your coins is strictly larger than the sum of values of the remaining coins that your twin will have. However, you correctly thought that if you take too many coins, the twin will suspect the deception. So, you've decided to stick to the following strategy to avoid suspicions: you take the minimum number of coins, whose sum of values is strictly more than the sum of values of the remaining coins. On this basis, determine what minimum number of coins you need to take to divide them in the described manner.

Input

The first line contains integer n (1 ≤ n ≤ 100) — the number of coins. The second line contains a sequence of n integers $a_1, a_2, ..., a_n (1 ≤ a_i ≤ 100) $ — the coins' values. All numbers are separated with spaces.

Output

In the single line print the single number — the minimum needed number of coins.

Examples

input

2
3 3

output

input

3
2 1 2

output

Note

In the first sample you will have to take 2 coins (you and your twin have sums equal to 6, 0 correspondingly). If you take 1 coin, you get sums 3, 3. If you take 0 coins, you get sums 0, 6. Those variants do not satisfy you as your sum should be strictly more that your twins' sum.

In the second sample one coin isn't enough for us, too. You can pick coins with values 1, 2 or 2, 2. In any case, the minimum number of coins equals 2.

思路：从大到小排序后，一个一个加上并判断是否满足条件。

python

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = 0
c = sum(a)
k = 0
for i in a:
    b += i
    k += 1
    if b > c/2:
        break
print(k)

这段代码的目标是找出最少数量的硬币，使得这些硬币的总值大于所有硬币总值的一半。为了实现这个目标，它首先对硬币按照价值进行降序排序，然后依次累加硬币的值，直到总值超过所有硬币总值的一半。下面是对这段代码的时间复杂度分析：

输入处理：
- n = int(input())：读取输入的硬币数量，时间复杂度为 O(1)。
- a = list(map(int, input().split()))：读取并转换成整数列表，时间复杂度为 O(n)。
排序：
- a.sort(reverse=True)：对硬币列表按降序排序。排序操作的时间复杂度通常为 O(n log n)，其中 n 是列表中的元素数量。
求和：
- c = sum(a)：计算所有硬币的总值，时间复杂度为 O(n)。
累加和判断：
- for i in a:：遍历排序后的硬币列表，时间复杂度为 O(n)。但在实际运行中，由于存在 if b > c/2: break 的条件，循环可能会提前终止，具体取决于硬币的分布情况。然而，在最坏的情况下，这个循环仍然需要遍历整个列表，所以时间复杂度仍为 O(n)。

综合以上各部分，这段代码的时间复杂度主要由排序操作决定，即 O(n log n)。这是因为排序操作的时间复杂度通常高于其他部分的操作，如输入处理、求和和累加判断等。

python

n = int(input())
coins = [int(i) for i in input().split()]
fq = 101*[0]    #skip index 0
 
nSum = 0
for i in range(n):
        nSum += coins[i]
        fq[int(coins[i])] += 1
 
avg = nSum//2
 
n_coin = 0
value_n_coin = 0
 
stop_value = 0
for value in range(100,0,-1):
        if fq[value]==0: continue
 
        if fq[value]*value + value_n_coin > avg :
                stop_value = value
                break
 
        value_n_coin += fq[value]*value
        n_coin += fq[value]
 
for i in range(1,fq[stop_value]+1):
        if i*stop_value + value_n_coin > avg :
                n_coin += i
                break
 
print(n_coin)

这段代码实现了一个算法，用于解决一个特定的问题：给定一组硬币（每个硬币有一个非负整数值），目标是选择最少数量的硬币，使这些硬币的总值至少达到所有硬币总值的一半。这个算法的时间复杂度主要由几个部分组成：

输入处理：n = int(input()) 和 coins = [int(i) for i in input().split()] 这两行代码用于读取输入数据。这里的时间复杂度为 O(n)，因为需要遍历一次输入的字符串来创建列表 coins。
频率数组初始化与填充：fq = 101*[0] 初始化一个大小为101的列表，用于存储每个可能的硬币值出现的次数（假设硬币值范围在1到100之间）。接着，通过循环 for i in range(n): 遍历所有硬币，更新它们在 fq 中对应的计数。这一部分的时间复杂度也是 O(n)。
计算平均值：avg = nSum//2 计算所有硬币总值的一半。这里的操作是常数时间复杂度 O(1)。
寻找停止值：接下来的循环 for value in range(100,0,-1): 从最大可能的硬币值开始，向最小值方向遍历，直到找到第一个满足条件的硬币值，即 fq[value]*value + value_n_coin > avg。这部分最坏情况下的时间复杂度为 O(100)，即 O(1)，因为循环最多执行100次。
确定最终硬币数量：最后一个循环 for i in range(1,fq[stop_value]+1): 用于确定在达到或超过平均值时需要添加多少个 stop_value 硬币。最坏情况下，这将执行 fq[stop_value] 次，但由于 fq[stop_value] 最多为 n，因此这部分的时间复杂度为 O(n)。

综上所述，整个算法的主要时间消耗在于输入处理和频率数组的填充上，即 O(n)。其他部分的时间复杂度要么是常数级别的，要么与硬币值的范围相关（在这里固定为100，因此可以视为常数时间）。因此，该算法的整体时间复杂度为 O(n)。

这个算法有效地解决了问题，因为它通过首先考虑高价值的硬币来尽可能快地达到目标值，从而确保了选择的硬币数量最少。

160A. Twins ​

160A. Twins