Problem 0539 : Pizza

問題概要

日本語なので本文参照
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0539

解法

二分探索。
ピザ屋は座標でソートしておけば、二分探索により最寄の店を求めることができる。
(lower_boundで座標が配達先以上のノードを取り、それか一つ直前のノードが最寄の店)


配達先もソートしておくと尺取メソッド的なことができるけど計算量はほとんど変わらない気がする。
(O((n+m)log n)がO(nlog n+mlogm)になって微妙に得?)

ソースコード

int dd,n,m,d[100002],k;

int main()
{
	int test[10];
	rep(i,10)test[i]=2*i;
	
	while(scanf("%d",&dd),dd){
		scanf("%d%d",&n,&m);
		rep(i,n-1)scanf("%d",d+i);
		d[n-1]=dd; d[n++]=0; sort(d,d+n);
		int ans=0;
		rep(i,m){
			scanf("%d",&k);
			if(!k)continue;
			int p=lower_bound(d,d+n,k)-d;
			ans+=min(d[p]-k,k-d[p-1]);
		}
		printf("%d\n",ans);
	}
	return 0;
}