# AtCoder Regular Contest 006

URL: https://atcoder.jp/contests/arc006/ (opens new window)

# C

n = gets.chomp.to_i

# 各山の一番上に乗っている箱の重さ
arr = []

n.times do
  w = gets.chomp.to_i
  index = nil
  w_diff = 10 ** 5
  # 一番重さの差が小さいところを探る
  arr.each_with_index do |a, i|
    next if w > a # 軽くないとだめ
    diff = a - w
    if diff < w_diff
      w_diff = diff
      index = i
    end
  end
  if index.nil?
    # 山を追加
    arr << w
  else
    # 山の上に乗せる
    arr[index] = w
  end
end

puts arr.length
Last Updated: 2020/08/09 18:33