AGC-011-B Colorful Creatures

■■■問題■■■

すぬけ君は，N匹の変わった生き物を見つけました．
それぞれの生き物には色と大きさが定まっており，
i番目の生き物の色はi，大きさはAiで表されます．

どの生き物も，大きさが自分の2倍以下であるような他の生き物を吸収することができます．
大きさA，色Bの生き物が大きさC，色Dの生き物を吸収すると (C <= 2×A)，
合体して大きさ A+C，色Bの生き物になります．

ここで，2匹の生き物の大きさによっては，
どちらも他方を吸収することが可能な場合があります．

すぬけ君がこの生き物たちを観察していると，
合体を繰り返して，最終的に1匹になりました．
このとき，残った生き物の色として考えられるものは何種類あるかを求めてください．

■■■入力■■■

N
A1 A2 ・・・ AN

●2 <= N  <= 10万
●1 <= Ai <= 10億
●Aiは整数

■■■出力■■■

この生き物たちが合体を繰り返して，最終的に1匹になったとき，
残った生き物の色として考えられるものは何通りあるかを出力せよ．

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("3 1 4");
            //2
            //最終的に残った生き物の色としては色1,3が考えられます．
            //例えば，色3の生き物が色2の生き物を吸収し，
            //次に色1の生き物が色3の生き物と合体すると，色1の生き物のみが残ります．
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("1 1 1 1 1");
            //5
            //同じ大きさの生き物が複数いる場合もあります
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6");
            WillReturn.Add("40 1 30 2 7 20");
            //4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] AArr = InputList[1].Split(' ').Select(X => long.Parse(X)).ToArray();
        Array.Sort(AArr);

        long Ruisekiwa = 0;
        bool HasBundan = false;
        int BundanInd = 0;
        for (int I = 0; I <= AArr.GetUpperBound(0) - 1; I++) {
            Ruisekiwa += AArr[I];

            if (Ruisekiwa * 2 < AArr[I + 1]) {
                HasBundan = true;
                BundanInd = I;
            }
        }
        if (HasBundan) Console.WriteLine(AArr.Length - BundanInd - 1);
        else Console.WriteLine(AArr.Length);
    }
}

解説

昇順にソートしておいて、
累積和*2 < 配列の値
を満たす、最大の添字を求めてます。