Tips. 平均値や中央値の最大化には二分探索が有効
平均値としてあり得る値の最大値
入力例1のとき、次の図のように考えられる。
max_sum は B の隣り合う値の少なくとも一方を選択したときの、選択した値の和とする。
max_sum は簡単なdpを行うことで求められる。
平均値としてあり得る値の最大値は近似値を求めればよいので、 となるまで二分探索を行う。
中央値としてあり得る値の最大値
入力例2のとき、次の図のように考えられる。
B を下図のように定義することで、平均値のときと同様にして求めることができる。
