問題
B - Range Point Distance
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
提出
Submission #44642798 - AtCoder Regular Contest 129
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
解けた
以下、解法を書く。
整数ペアが2つの場合を考えてみる。
このとき、考えられる区間のパターンは2通りで、 $L_1<L_2<R_1<R_2$と$L_1<R_1<L_2<R_2$。
前者は区間が重なっている場合で、$max(dist(L1,R1,x),(L2,R2,x))$は0になる。
後者は区間が重なっていない場合で、$max(dist(L1,R1,x),(L2,R2,x))$は$R_1$と$L_2$の中間になる。
つまり、区間が2つの時$max(0,(L_2-R_1)/2)$になる。
整数ペアが複数ある場合、それぞれ2ずつに着目すると、距離は$max(0,(L_i-R_j)/2)$になる。
これが最大になるペアは$L_{max}$と$R_{min}$になる。
入力の$L,R$それぞれで$L_{max},R_{min}$を算出し$max(0,(L_{max}-R_{min})/2)$を出力する。
(L_{max}-R_{min})/2は切り上げする必要がある。
コメント