AOJ2104 Country Road

問題リンク Country Road

• 解法

発電機を置く座標を考える必要は全くありません。その発電機によって電力が供給される家の範囲を考えます。1台のとき、1〜Nの家全てをカバーするので電線の長さはx_N-x_1です。発電機がもう1台あったとき、x_1 〜 x_k と x_k+1 〜 x_Nの範囲をそれぞれカバーすることになります。これによって削減できる電線の長さはx_k+1 - x_kとなるので、隣接距離が最も大きいkとk+1を選べば良いことが分かります。つまり、隣接距離を降順でソートして、発電機の台数がある限り、引いていけば電線の長さが最小になります。

• ソース

import java.util.Arrays;
import java.util.Scanner;

//Country Road
public class AOJ2104 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while(T--!=0){
			int n = sc.nextInt(), k = sc.nextInt();
			int[] a = new int[n], len = new int[n-1];
			for(int i=0;i<n;i++)a[i] = sc.nextInt();
			for(int i=0;i<n-1;i++)len[i]=a[i+1]-a[i];
			Arrays.sort(len);
			int res = a[n-1]-a[0];
			int j = n-2;
			while(j>=0&&--k!=0)res-=len[j--];
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2104().run();
	}
}