Codeforces #244 Div2 E. Police Patrol

本番は凡ミスで落としたけど、それは置いといてC,Dより簡単なような…。
http://codeforces.com/contest/427/problem/E

問題

1次元数直線上にN人の犯罪者がいる。
数直線上に1か所警察署を作り、そこからパトカーを出してN人を回収したい。
パトカーには1回で最大M人まで載せることができる。

警察署を作る位置を最適化し、パトカーの移動量を最小化せよ。

解法

警察署の位置を三分探索で求めればよい。

警察署の位置さえ決まれば、後は一番犯罪者を捕まえに行って、帰り際に遠い順に計M人まで捕まえてくれば良い。

int N,M;
int A[1000001];

ll hoge(ll pos) {
	int L=0,R=N-1;
	ll tot=0;
	while(L+M<=N-1 && A[L+M]<pos && L+M<=R) tot+=2*abs(A[L]-pos), L+=M;
	while(R-M>=0 && A[R-M]>pos && L<=R-M) tot+=2*abs(A[R]-pos), R-=M;
	
	if(A[R]>pos) tot+=2*(A[R]-pos);
	if(A[L]<pos) tot+=2*(pos-A[L]);
	return tot;
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	
	ll L=-1000000000;
	ll R=1000000000;
	ll mi=1LL<<60;
	FOR(i,100) {
		ll po1=(L*2+R)/3;
		ll po2=(L+R*2)/3;
		
		ll tot1=hoge(po1);
		ll tot2=hoge(po2);
		mi=min(mi,tot1);
		mi=min(mi,tot2);
		if(tot1==tot2) L=po1,R=po2;
		if(tot1<tot2) R=po2;
		if(tot1>tot2) L=po1;
	}
	
	cout << mi << endl;
}

まとめ

せっかくあっさり解けたのに、しょうもない配列外参照ミス、これはもったいないな。