「2100～2110」の編集履歴（バックアップ）一覧に戻る

2100～2110 - (2011/09/09 (金) 16:01:49) のソース

----
*2104　Country Road
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2104
発電機の数と電線が与えられるので全ての家に電気を供給する問題。
家は一本の道沿いに並んでおり電線は道沿いに敷設することとし、電線の長さが最小になるように敷設するという問題です。

解法
全部の家を電線でつなげた状態から分断していくという視点で見ればこの問題は非常に簡単になります。
一番長い電線を発電機の数-1か所切断すれば答えが出てきます。


 #include<stdio.h>
 #include <algorithm>
 #include <functional>
 int house[100001];
 void setData(){
	int h,k,sum=0,t1,t2;
	scanf("%d %d %d",&h,&k,&t1);
	for(int i=1;i<h;i++){
		scanf("%d",&t2);
		house[i-1]=t2-t1;
		sum+=t2-t1;
		t1=t2;
	}	
	if(k>=h){
		printf("0\n");
	}else{
		std::sort(house,house+h-1,std::greater<int>());
		for(int i=0;i<k-1;i++){
			sum-=house[i];
		}
		printf("%d\n",sum);
	}
 }
 int main(){
	int n;
	scanf("%d",&n);
	while(n--)setData();
 }