問題概要
$N \ $個の区画に$ \ M \ $個のマンションがあり、$p_i \ $番目の区画には高さ$ \ h_i \ $のマンションがある。
空いている$ \ N - M \ $個の区画について以下の条件を満たすようにマンションを建てるとき、建てることのできるマンションの高さの総和の最大値を求めよ。
- 建設するマンションの高さは$ \ H \ $以下でなくてはならない。
- $i \lt j \ $を満たす整数$ \ j \ $について、$i \ $番目のマンションは$ \ j \ $番目のマンションよりも高くなくてはならない。
制約
- $2 \leq N \leq 10^6$
- $0 \leq M \leq N$
- $1 \leq H \leq 10^9$
解説
この問題では左の区画からできるだけ高いマンションを建てていくように貪欲的に答えを求めていくことができます。
区画$ \ k \ (1 \leq k \leq N) \ $には、既にマンションが存在する場合はマンションを建設することはできません。
存在しない場合は、「区画$ \ k \ $よりも左で最も近くにあるマンションの高さ」よりも低く、「区画$ \ k \ $よりも右で最も近くにあるマンションの高さ」よりも高くする必要があります。
よって、左右それぞれのマンションの高さを$ \ h_l,h_r \ $としたとき、$h_l \gt X \gt h_r \ $を満たす整数$ \ X \ $が存在するならば高さが$ \ h_l \gt X \gt h_r \ $を満たす最大の$ \ X \ $となるマンションを建設します。 そうでない場合は建設しません。 ただし、左にマンションがない場合は$ \ h_l = H + 1 \ $、右にマンションがない場合は$ \ h_r = 0 \ $とします。
左から順番に見ていくので$ \ h_l \ $は簡単に求まります。$ \ h_r \ $については右から累積maxを取っておくなどすれば高速に求めることができます。
よって、この問題は時間計算量$ \ O(N) \ $で解くことができます。
