[Sart]Boj 1597:矢印を描く

[Sart]Boj 1597:矢印を描く

link: https://www.acmicpc.net/problem/15970

質問する

位置が直線上の0、1、2...等非負の数の整数を一定の間隔で右に置きます.これらの位置の各位置には点があります(<図1>).指定点の位置が違います.2点間の距離は、2点位置の数の差を表します.<図1>には4つの点が与えられ、点aとbの距離は3である.

各点にN色のうちの1つがあります.私服、色は1からNの数字で表します.
各点pについて、pから始まる直線矢印を用いて別の点qに接続しようとする.ここで、点qはpのような色の点の中でpに最も近い点であるべきである.最近の点が2つ以上あれば、勝手に1つ選んでください.
各点について、常に同じ色の異なる点が存在します.したがって、上記の条件を満たすqまで、各点pから常に矢印を描くことができる.
例えば、点を順次対(位置、色)と表記する場合、a=(0,1)、b=(1,2)、c=(3,1)、d=(4,2)、e=(5,1)と呼ぶ.
以下の<図2>にこれらの点を表示します.ここで、白は1に相当し、黒は2に相当する.

上記の条件で矢印を描画すると、図3に示すように、点aの矢印がcに接続されます.点bとdの矢印は、それぞれdとbに接続されている.また、点cとeの矢印は、それぞれeとcに接続されている.したがって、すべての矢印の長さは、3+3+2+2=13です.

ポイントの位置と色を指定すると、ライタはすべてのポイントから始まる矢印の長さとを出力します.

入力

標準入力、以下の情報を提供します.最初の行は、点の個数を表す整数Nを与える.次のN行では、点座標と色を表す2つの整数xとyがそれぞれ与えられる.

しゅつりょく

標準出力で、すべての点から始まる矢印の長さと出力します.

制限

のすべてのサブタスクにおいて、点の位置xおよび色yは、それぞれ0≦x≦105、1≦y≦Nを満たす.

I/O例

コード|Python

import sys
si = sys.stdin.readline

answer = 0
N = int(si())
AB = [[] for _ in range(N)]
dict_AB = {}

#dictionary에 색별로 좌표 저장하기
for i in range(N):
    AB[i] = list(map(int,si().split()))
    if AB[i][1] in dict_AB:
        dict_AB[AB[i][1]].append(AB[i][0])
    else:
        dict_AB[AB[i][1]] = [AB[i][0]]

#왼쪽 좌표와의 거리
def left(list_,i):
    if i == 0: return 100000
    else: return list_[i] - list_[i-1]

#오른쪽 좌표와의 거리
def right(list_,i):
    if i == len(list_)-1: return 100000
    else: return list_[i+1]-list_[i]

#dictionary에 각 색별 최소거리 계산 후 정답
for value in sorted(dict_AB.values()):
    temp = sorted(value)
    sum = 0
    for i in range(len(temp)):
        sum += min(left(temp,i),right(temp,i))
    answer += sum

print(answer)

Screenshot & Output