algoNote

プログラミング関連

Codeforces Round #433 Div.2D / Div.1B . Jury Meeting

問題文

codeforces.com

解法

K日間の開始日をd日目としたとき、1〜Nの陪審は1日目からd日目の間に出発する最も安い便で移動するべきである。

開始日をd日目とすると解散する日はd+K日目で、行きと同様に1〜Nの陪審はd+k+1日目以降に出発する便のうち最も安い便で帰るべきである。

  • cost1[d] := 1〜d日目までに出発する便のうち、1〜Nそれぞれの最安の便のコストの和 (不可能なら-1)
  • cost2[d] := d日目以降に出発する便のうち、1〜Nそれぞれの最安の便のコストの和 (不可能なら-1)

となるcost1,cost2を予め計算しておけば、min(cost1[d]+cost2[d+k+1])をすべてのdについて調べることで答えを求められる。

コード

  • 和を持っておいて、最小値が更新されるときに旧の値を引いてから新しい値を足す
  • cost1は左から、cost2は右から構築していくイメージ

853B - Jury Meeting : http://codeforces.com/proble ...