【プログラミングコンテスト】AtCoder Beginner Contest 115③

昨日東京から福岡に帰ってきました、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc115)にて開催されました、AtCoder Beginner Contest115の第3問「C - Christmas Eve」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

とある世界では、今日はクリスマスイブです。

高羽氏の庭には N 本の木が植えられています。 i 本目の木 ( 1 ≤ i ≤ N ) の高さは h i メートルです。

彼は、これらの木のうち K 本を選んで電飾を施すことにしました。より美しい光景をつくるために、できるだけ近い高さの木を飾り付けたいです。

より具体的には、飾り付ける木のうち最も高いものの高さを h m a x メートル、最も低いものの高さを h m i n メートルとすると、 h m a x − h m i n が小さいほど好ましいです。 h m a x − h m i n は最小でいくつにすることができるでしょうか？

2.入力例

• 入力

5 3
10
15
11
14
12

• 出力

2

3.初見の感想

• K個選んで最も差が小さくなるようにしたい
• 高さでのソーティングが有効そう

4.コードの簡単な解説

• 入力を配列に保管

 public static void Main(){
      String[] temp=System.Console.ReadLine().Split(' ');
      int treeNum=int.Parse(temp[0]);
      int choiceTreeNum=int.Parse(temp[1]);
      int[] treeHigh=new int[treeNum];
      for(int i=0;i<treeNum;i++){
      treeHigh[i]=int.Parse(System.Console.ReadLine());
      }

• ソートを行う

      Array.Sort(treeHigh);

• K個差の要素を比較して最小値を求める

      int dif=int.MaxValue;
      for(int i=0;i<=treeNum-choiceTreeNum;i++){
      dif=Math.Min(dif,treeHigh[i+choiceTreeNum-1]-treeHigh[i]);
      }
      System.Console.WriteLine(dif);

5.全コード

using System;
 
class Sample{
    public static void Main(){
      String[] temp=System.Console.ReadLine().Split(' ');
      int treeNum=int.Parse(temp[0]);
      int choiceTreeNum=int.Parse(temp[1]);
      int[] treeHigh=new int[treeNum];
      for(int i=0;i<treeNum;i++){
      treeHigh[i]=int.Parse(System.Console.ReadLine());
      }
      Array.Sort(treeHigh);
      int dif=int.MaxValue;
      for(int i=0;i<=treeNum-choiceTreeNum;i++){
      dif=Math.Min(dif,treeHigh[i+choiceTreeNum-1]-treeHigh[i]);
      }
      System.Console.WriteLine(dif);
    }
}

6.最後に

入力例から出力をどう選んでいるかの操作を、手続き操作に落とし込めるようになってきました(^^)