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; }