JOI本選 - ピザ

JOI 2009 本選2問目

ピザ | Aizu Online Judge (AOJ-0539)

問題概要

長さ d の円周上に n個 の店舗と m個 の宅配先があり、配達先にはそれぞれもっとも近い店舗から配達する。そのときの合計の移動距離は何か。

・1 < d <= 10 ^9

・1 < n <= 10 ^5

・1 < m <= 10 ^4

解法

円周上のままだと考えにくいので最初の店舗が両端にあるような線分上で考える。

配達先の両隣であるような店舗を二分探索で求め、配達先から近いほうの距離を加算していく。(店舗の与えられる順番はランダムなのであらかじめソートしておく)

提出したコード

AIZU ONLINE JUDGE: Code Review

感想

微妙に遅いコードを書いてしまった(0.04sec)

問題自体はやるだけだったので数分でAC

非公式難易度表の難易度5からはブログに書いていこうと思っていたのにすでに難易度5と6の予選問題を埋めていて悲しかったです