[BOJ]15970矢印描画/ベースソートアルゴリズム

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に相当する.

-入力:標準入力で次の情報を取得します.最初の行は、点の個数を表す整数Nを与える.次のN行では、点座標と色を表す2つの整数xとyがそれぞれ与えられる.
各点が有する色cについて、色cを有する点は正確に2つ存在し、点の個数は2≦N≦10を満たす.
-サブタスク:
1)点の色はすべて同じで、点の個数は2≦N≦300を満たす.
2)点の色は正確に2種類に分けられ,点の個数は2≦N≦1000を満たす.
1)点の個数は2≦N≦5000を満たす.

💡 最も簡単な方法を考える

Aの配列が灰色を基準とする場合、A[i]およびA[j]が考慮される.
引き続きtemp変数でmin値を置き換え、最短距離を探します.

可能ですが、O(n^2)がタイムアウトする可能性があります.

📌 ソートによる解決

同じ色の痣だけを集める.
*プロパティを使用してソートする場合、隣接する場所はその両側にあります*
両側の数値の差が小さい値を矢印値に追加します.

1.同じ色の点を集める

		ArrayList<Integer>[] a=new ArrayList[N+1];
		for(int color=1;color<=N;color++)
			a[color]=new ArrayList<Integer>();

ArrayList配列値がN+1の理由は,0をNull値とし,1−Nビットを配置したためである.
以下、a[color]に該当する位置をArrayListとして追加する.

2.適切な位置の色を追加

		for(int i=0;i<N;i++) {
			coor=sc.nextInt();
			color=sc.nextInt();
			
			a[color].add(coor);
		}