きままにものづくり

日々の気付いたことなんかを書いてます。

SRM647Div1Easy

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13634

N個のビルを建設したい。与えられる制限は以下の4つ。

  • 高さは非負整数
  • 一つ目のビルの高さは0
  • 隣り合うビルとの高さの差分は最大で1
  • x_i番目のビルの高さは、t_i以下

ここで、x_iはビルの番号を示し、t_iはそのビルの高さの制限を示す。

解法

各ビルの最大の高さを計算し、その中の最大値が答えとなる。

計算量

 O(N|x|)

コード

広告を非表示にする