[15970]描画矢印

🔗 質問リンク

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です.

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

⚠▼制限

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

🗝 プール(言語:Java)

座標と色を持つ2 D配列を作成し、色を基準とし、座標の昇順を基準として並べ替えます.繰り返しの過程で、両端座標の箱は隣接座標との距離だけを計算し、中間座標は左右座標の色を比較し、両側が同じであれば座標距離差が最も小さい座標で、片側が同じであれば、相応の座標距離だけを加えると正解を求めることができる.時間の複雑さはArrayssort()の使用はO(Nlogn)O(Nlogn)O(Nlogn)であるべきである.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
    private int drawArrow(int n, int[][] arr) {
        int answer = 0;
        // 색깔 기준으로 정렬하되, 같으면 좌표 오름차순으로 정렬
        Arrays.sort(arr, (o1, o2) -> {
            if (o1[1] == o2[1])
                return o1[0] - o2[0];
            else
                return o1[1] - o2[1];
        });
        // 반복문 돌면서 체크
        for (int i = 0; i < n; i++) {
            // 시작 좌표는 오른쪽 옆 점과의 거리
            if (i == 0) {
                answer += (arr[1][0] - arr[0][0]);
            // 마지막 좌표는 왼쪽 옆 점과의 거리
            } else if (i == n - 1) {
                answer += (arr[n-1][0] - arr[n-2][0]);
            } else {
                // 왼쪽 오른쪽 같은 색이면 좌표 거리차이 최소값
                if (arr[i][1] == arr[i-1][1] && arr[i][1] == arr[i+1][1])
                    answer += Math.min(arr[i][0] - arr[i-1][0], arr[i+1][0] - arr[i][0]);
                // 왼쪽만 같은 색
                else if (arr[i][1] == arr[i-1][1])
                    answer += (arr[i][0] - arr[i-1][0]);
                // 오른쪽만 같은 색
                else
                    answer += (arr[i+1][0] - arr[i][0]);
            }
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i] = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
        }
        br.close();
        Main main = new Main();
        System.out.print(main.drawArrow(n, arr));
    }
}