AtCoder Grand Contest 011 B – Colorful Creatures をPython3で解く

# AtCoder Grand Contest 011 B - Colorful Creatures
# https://atcoder.jp/contests/agc011/tasks/agc011_b
# tag: 事前ソート 累積和 考察

# 小さいものから順番に、ひとつ上の大きなものを吸収させていき、
# 吸収できなくなれば一旦ストップ・次のものを最初にして
# 再スタート。どこかから最後まで行き着くことができれば、
# 最後に再スタートしたところ～最後のどの色にもなることが
# できる……みたいな。

# 例えば、
# 1, 2, 3, 100, 200, 300 という大きさの生物がいるとしたら、
# 1, 2, 3 は、どう頑張っても最後に残ることが出来ない。
# その条件は、(1 + 2 + 3) * 2 が 100 未満であること。
# 逆に、100, 200, 300 については 
# 100←6, (100+6)←200, (100+6+200)←300
# と食べさせることで、100 を最後に残すことができるが、
# この場合 100 を 200 や 300 と入れ替えても同順の
# 捕食が可能なので、100, 200, 300 のどれでも最後に残せる。

# 吸収できるかどうかはそれまでに吸収したもの全ての大きさの
# 合計が関わってくるので、累積和を使用すると楽。

def main():
    N = int(input())
    A = list(map(int, input().split()))

    # ソートして累積和を取る
    A.sort()
    csum = []
    tmp = 0
    for a in A:
        tmp += a
        csum.append(tmp)

    start = 0
    now = 1
    while True:
        if now == N:
            break
        # 一つ前までの合計で、今考慮している生物を吸収可能かどうか
        if csum[now - 1] * 2 >= A[now]:
            now += 1
        else:
            start = now
            now += 1
    
    print(N - start)

main()