AGC-011-A Airport Bus

■■■問題■■■

高橋空港には，毎日飛行機でN人の乗客が到着します．
i番目の乗客は時刻Tiに到着します．

高橋空港に到着する乗客は全員バスで市内へ移動します．
どのバスも定員はC人であり，C人以下の乗客を乗せることができます．

飛行機の乗客は，飛行機の到着時刻よりも早く出発するバスには乗ることができません．
また，飛行機の到着時刻からKの時間が経過した後にもバスに乗れていないと，怒り出してしまいます．

そのため，i番目の乗客は，
出発時刻が Ti 以上 Ti+K 以下であるようなバスに乗れるようにしないといけません．

この条件のもとで，うまくバスの出発時刻を定めるとき，
必要なバスの数の最小値を求めてください．
ただし，バスの出発時刻は必ずしも整数である必要はなく，
同じ時刻に出発するバスが複数あってもかまいません．

■■■入力■■■

N C K
T1
T2
・
・
・
TN

●2 <= N  <= 10万
●1 <= C  <= 10億
●1 <= K  <= 10億
●1 <= Ti <= 10億
●C,K,Ti は整数

■■■出力■■■

必要なバスの数の最小値を出力せよ．

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("5 3 5");
            WillReturn.Add("1");
            WillReturn.Add("2");
            WillReturn.Add("3");
            WillReturn.Add("6");
            WillReturn.Add("12");
            //3
            //例えば，時刻 4.5, 6, 12 にバスを出発させ，次のように乗客をバスに乗せるとよいです．
            //●時刻 4.5 に出発するバスには，時刻 2,3 に到着する乗客を乗せる．
            //●時刻 6 に出発するバスには，時刻 1,6 に到着する乗客を乗せる．
            //●時刻 12 に出発するバスには，時刻 12 に到着する乗客を乗せる．
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 3 3");
            WillReturn.Add("7");
            WillReturn.Add("6");
            WillReturn.Add("2");
            WillReturn.Add("8");
            WillReturn.Add("10");
            WillReturn.Add("6");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int N = wkArr[0];
        int C = wkArr[1];
        int K = wkArr[2];

        int[] TArr = InputList.Skip(1).Select(X => int.Parse(X)).ToArray();
        Array.Sort(TArr);

        var JyoukyakuList = new List<int>();
        int NeedBusCnt = 0;
        foreach (int EachT in TArr) {
            bool WillClear = false;

            //バスの定員に達している場合
            if (JyoukyakuList.Count == C) WillClear = true;

            //待ち時間を超える場合
            if (JyoukyakuList.Count > 0) {
                if (JyoukyakuList[0] + K < EachT) WillClear = true;
            }

            if (WillClear) {
                JyoukyakuList.Clear();
                NeedBusCnt++;
            }

            JyoukyakuList.Add(EachT);
        }
        NeedBusCnt++;
        Console.WriteLine(NeedBusCnt);
    }
}

解説

ナイーブにシュミレーションしつつ、貪欲法を使ってます。