白駿18310-アンテナ

1354 ワード
白駿 グリディ テキストリンク

質問する


一直線上の村には何軒も家がある.その中で特定の位置の家にアンテナを特別に取り付けることにした.効率を高めるために、アンテナからすべての家までの距離の合計を最小限に設定します.この場合、アンテナは家のある場所にしか取り付けられず、論理的には同じ位置に複数の家が存在することができる.
家屋の位置値を指定する場合は、アンテナをインストールする場所を選択するプログラムを作成します.
例えば、N=4とし、各位置は1、5、7、9である.

この場合、5の位置に取り付けた場合、アンテナからすべての家までの距離の合計は(4+0+2+4)=10となり、最小となる.

入力


1列目の家の数Nは自然数です.(1≦N≦200000)2行目はN棟の家の空白を基準に区分され、1以上100000以下の自然数で与えられる.

しゅつりょく


1行目に設置アンテナ位置の値を出力します.ただし、実装アンテナの位置値として複数の値を導出すると、最小値が出力される.

Solution


Java

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

public class Baek18310 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] house = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            house[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(house);
        System.out.println(house[(N-1)/2]);
    }
}
ソート後に中心値をエクスポートする問題.二重砲口で距離を蓄えたところ、タイムアウトした.
マルチスレッド-同期ロック
getStaticPathsに関連