Codeforces Round #317 Div1 B: Minimization
解法
「N人をK個のグループに分ける。グループの人数はN/KまたはN/K+1でなければならない。グループの人間を身長順にソートした時の隣接する2人の身長の差の合計を、グループのコストとする。グループのコストの合計の最小値はいくつか?」という問題に読み替える。
グループのコストは、一番大きい人と一番小さい人の差であることに気付く。なのでグループ内の身長はできるだけ近いほうが良い。
新しくグループを作る時にグループ内で一番小さい人を決めると、グループの人数をN/Kにするか、それともN/K+1にするか、ということが問題になる。それぞれの場合について動的計画法で求めてやれば良い。
コード
import java.util.Arrays; import java.util.Scanner; public class Main { private final long INF = Long.MAX_VALUE / 4; public void solve() { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int groups = scanner.nextInt(); int[] A = new int[N]; for (int i = 0; i < N; i++) { A[i] = scanner.nextInt(); } Arrays.sort(A); int member = N / groups; int bigGroups = N % groups;// メンバーが1人多いグループの数 long[] dp = new long[groups + 1]; Arrays.fill(dp, INF); dp[0] = 0; long[] dp2 = new long[groups + 1]; // dp[groupNum][bigNum]:=groupNum個グループを作った時、bigNum個bigGroupを作った時の最小値 for (int groupNum = 1; groupNum <= groups; ++groupNum) { Arrays.fill(dp2, INF); for (int bigs = bigGroups; bigs >= 0; bigs--) { // bigsは今までに作ったbigGroupの数 int start = (groupNum - 1) * member + bigs; // 新しく作るグループがbigGroupでない場合 int cost = Math.abs(A[start + member - 1] - A[start]); dp2[bigs] = Math.min(dp[bigs] + cost, dp2[bigs]); // 新しく作るグループがbigGroupある場合 if (bigs == bigGroups) { continue; } int bigCost = Math.abs(A[start + member] - A[start]); dp2[bigs + 1] = Math.min(dp2[bigs + 1], dp[bigs] + bigCost); } // コピーする for (int j = 0; j <= groups; j++) { dp[j] = dp2[j]; } } System.out.println(dp[bigGroups]); scanner.close(); } public static void main(String[] args) { new Main().solve(); } }