AtCoder Regular Contest #004 B. 2点間距離の最大と最小

その他

問題

平面上にN+1個の点があり、i番目とi+1番目の間の距離diがN個与えられる。
1番目とN+1番目の点の距離でとりうる最大値と最小値を返す。

考え方

最大値は、一直線に並べたときが最大なので、距離の総和が答え。
最小値は、自明なものとして、N=1のときはd0、N=2のときはd0-d1の絶対値。

N>=3のときを考える。

距離の中で、最大の長さのものをd_maxとすると、(距離の総和-d_max)<=d_maxの場合、d_maxとなっているところがどこであろうと距離を0にすることはできない。
一番近づくときは、(距離の総和-d_max-d_max)の時なので、それを返す。

(距離の総和-d_max)>d_maxの場合、かならず多角形のように作ることができることがわかるので、最小値は0にできる。