読者です 読者をやめる 読者になる 読者になる

君はまるで砂漠に咲く、一輪の花。

僕はその花に引き寄せられる蝶。

Codeforces Round #Pi (Div.2)

はい。
http://codeforces.com/contest/567

A. Lineland Mail

ざっくりと大意

・直線上に座標に都市が並んでいて都市間で郵便料金は座標の離れている距離に等しい
・最小と最大の郵便料金がいくらか??

方針のようなもの

・全部調べる

python

n=int(raw_input())
x=map(int,raw_input().split())
l=[0]
tmp=0-x[0]
for i in range(1,n):
    l.append(l[-1]+abs((x[i]+tmp)-(x[i-1]+tmp)))
for i in range(n):
    if i==0:
        print l[1],l[-1]
    elif i==n-1:
        print l[-1]-l[-2],l[-1]
    else:
        print min(l[i]-l[i-1],l[i+1]-l[i]),max(l[i],l[-1]-l[i])

左端0番目の時は一つ右隣りが最小で最右端が最大。 右端最終番目の時は一つ左隣りが最小で0番目のが最大。中間にある要素は左右隣のどちらが最小か、左端右端のどちらが遠いかを調べる。累積和を調べておけば毎回端まで調べに行くよりは計算量がマシだと思う。