[BaekJoon/Java]BaekJoon 2212センサー

問題の概要

センサがx座標軸上の任意の点に位置する場合、各センサを管理するためにk個の集中局を設定する必要がある.この時、各集の中国は管理範囲の協議の最高価格を求めなければならない.問題の説明は少し難しいが、すべてのセットの中国が管理しなければならない範囲ではない.

アイデア

k個セット中国を設定すると,k個センサが集まる集合が容易に生成される.すなわち,センサをk個の集合に分割し,各集合が座標上に占める長さ(集合のうち最も右のセンサ−集合のうち最も左のセンサ)の和を求める.絵の説明は以下の通りです.

6つのセンサがあり、2つの集中管理が必要です.
センサの位置が赤色の円である場合、センサ間の間隔は緑色の数字と見なすことができる.サンプル入力では2つのコレクタであるため、これらのセンサを2つのコレクタに分け、各コレクタ長の和がコレクタ受信可能領域の最大値である.画像中のセンサを2つのグループに分けるために,最大の間隔を除いて2つのグループに分けることができる.そうであれば、除去3〜＞6のセンサ間のギャップが最大となる.
では,センサは(1,3)+(6,6,7,9)の2つのグループに分けられる.各束の長さ
(3-1)+(9-6)、これは5です.
すなわち,実装する必要がある集中点がk個であれば,各センサ間のギャップをアレイに格納してソートし,順次アレイからk−1個を削除し,残りのギャップを加算することで答えを得ることができる.
=>ギャップアレイ(0、1、2、2、3)から最大ギャップ3を削除し、残りのギャップを加算します.
(0+1+2+2)=5に等しい.

に答える

入力

のセンサを座標値ソートします.

各センサ間のギャップをgapアレイに装着し、昇順に並べた.

gap配列では、k−1要素を大きな順序で削除する.

を削除し、残りの要素をすべて追加します.

コード#コード#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] pos = new int[N];
        for(int i = 0; i < N; i++) {
            pos[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(pos);

        int[] gap = new int[N-1];
        for(int i = 0; i < N-1; i++) {
            gap[i] = pos[i+1] - pos[i];
        }
        Arrays.sort(gap);

        int sum = 0;
        for (int i = N-2-(K-1); i >= 0; i--) {
            sum += gap[i];
        }
        System.out.print(sum);
    }
}