裏紙

ほぼ競プロ、たまに日記

AOJ 2104 - Country Road

Country Road | Aizu Online Judge

・概要
n個の家に対してk個の発電機を設置してできるだけ電線を短くしよう
(n,k<=100000, 家の座標は0<=x<=1000000)

・アイデア
各家に対して,どの発電機から電気をもらうのがベストかといえば,一番近いやつだよな
n個のものをk組に分ける方法を考えてその端と端の距離の和が答えだ。
組み合わせはnCkだな...これは全探索したら多すぎる...

逆にその組み合わせではなく,間に注目してみる。
家がn個あるとき,家と家の間はn-1個,まず左端の家から右端の家までずっと電線が弾いてあると仮定して,その家と家の間からk-1個を選んでそこの電線をぶった切るって考えればいいんじゃね
そうすると電線はk本に分断されるからその1つ1つに発電機を置くと考えれば良い!
家と家の間の距離を保存しておいて,それをソートして大きい方からk-1個選んで全体から引けばおk!
これはO(n)だから動くぞ〜
ってかんじでした。後半のアイデアは高校の数学とかでもよく使う感じだよね。(思いつくのに30分くらいかかったけど)

・実装

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;

const long N=100000;

int main(){
	int t;
	scanf(" %d", &t);
	for(int times=0; times<t; ++times){
		long n, k, x[N];
		
		scanf(" %ld %ld", &n, &k);
		for(long i=0; i<n; ++i) scanf(" %ld", &x[i]);
		
		long bet[N];
		//bet[i]=distance between x[i] and x[i+1]
		for(long i=0; i<n-1; ++i) bet[i]=x[i+1]-x[i];
		sort(bet, bet+n-1, greater<long>());
		
		long ans=x[n-1]-x[0];
		for(long i=0; i<k-1; ++i) ans-=bet[i];
		
		if(ans<0) ans=0;
		
		printf("%ld\n", ans);
	}
}