B - 2点間距離の最大と最小 ( Maximum and Minimum )
時間制限 : 2sec / スタック制限 : 10MB / メモリ制限 : 64MB問題文
平面上に N+1 個の点があり、それぞれ 0 から N までの番号が付けられています。それぞれの点の位置はわかりませんが、0 以上 N 未満の整数 i について、
i 番の点と i+1 番の点の距離 di はわかっています。
0 番の点と N 番の点の距離としてとりうる値の最大と最小を求めてください。
入力
入力は以下の形式で標準入力から与えられる。N入力は N+1 行からなる。
d0
d1
:
dN−1
1 行目には点の番号の最大を表す整数 N (1 ≦ N ≦ 500) が与えられる。
2 行目から N+1行目までの i+2 行目 (0 ≦ i < N)には、
i 番と i+1 番の点の距離を表す整数 di(1 ≦ di ≦ 30,000) が与えられる。
出力
出力は標準出力に出力し、2 行からなる。1 行目には、0 番の点と N 番の点の距離としてとりうる最大値を出力せよ。
2 行目には、0 番の点と N 番の点の距離としてとりうる最小値を出力せよ。
誤差は絶対誤差あるいは相対誤差の少なくとも片方が 10^−3 以下であれば許容する。
なお、最後には改行を出力せよ。
出典
B: 2点間距離の最大と最小 ( Maximum and Minimum ) - AtCoder Regular Contest #004 | AtCoder回答
AtCoder/arc004_2.php at master · wada811/AtCoder · GitHub
最大は直線の場合だから合計すればいいとして最小が思いつかなかったから
他の人のC言語の回答を見たのだけれど見たら納得。何故思い浮かばなかったのかと…。
一番長い距離に対して他の距離の合計が大きいか小さかだけを考えれば良かったんだな…。
イメージは三節棍(すべての長さが同じだからちょっと違うけど)で、
一番長い距離に対してその他の合計のほうが小さければ直線的な距離の比較だし、
合計のほうが大きければ節の角度を変えて端をくっつければ最小の距離は0にできる。
コレは思い浮かべたかったなー。
てかPHPで配列のソートって簡単ですね。
ロジックだけわかれば書くことがほとんどなくて楽だけどアルゴリズムに弱くなりそう。