ABC024: C - 民族大移動

貪欲法

問題

C: 民族大移動 - AtCoder Beginner Contest 024 | AtCoder

N個ノードが存在する。K種類の民族がそれぞれS_iのノードに居る。 D日間以内に、各民族がT_iまで移動する。 i日目にはL_iからR_iまでのノードを行き来できる。 各民族について、最短日数を出力せよ。 すべての民族はD日以内に到達できることが保証されている。

  • 1 \le N \le 10^9
  • 1 \le D \le 10^4
  • 1 \le K \le 100
  • 1 \le L_i \le R_i \le N
  • 1 \le S_i, T_i \le N
続きを読む