けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 本選 2009 B - ピザ (AOJ 0539, 難易度 6)

ひょっとしたら難易度 5 との境界の問題だったかもしれない。lower_bound() を試すいい感じの例題。

問題概要

一周の長さが  D であるような周回コースがあって、コース上に  N 個の店舗がある。コース上の 1 点の座標を 0 とし、コースに沿って座標を設定する ( D = 0 となる)。

1 個目の店舗は座標 0 のところにあり、2 個目, 3 個目, ...,  N 個目の店舗の座標は  d_{2}, \dots, d_{N} で与えられる。

以下の  M 個のクエリに答えよ。 i 番目のクエリでは座標  k_{i} が与えられる。 k_{i} の位置からもっとも近いところにある店舗との距離を求めよ。

制約

  •  N \le 10^{5}
  •  M \le 10^{4}

考えたこと

店舗の座標は  0, d_{2}, d_{3}, \dots, d_{N} となる。あらかじめこれを座標順にソートしておくことにする。

各クエリ  k_{i} に対しては、配列  0, d_{2}, d_{3}, \dots, d_{N} の要素のうち、どの要素とどの要素との間にあるのかを二分探索 (C++ では lower_bound()) を用いて求めることができる。

なお、便宜上、店舗の座標に  D を末尾に加えておくと便利。これがちょうど番兵の役割を果たす。

計算量は  O((N+M) \log N) となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long D, N, M;
    cin >> D >> N >> M;
    vector<long long> a(N+1, 0);
    for (int i = 1; i < N; ++i) cin >> a[i];
    a[N] = D;
    sort(a.begin(), a.end());
    long long res = 0;
    for (int i = 0; i < M; ++i) {
        long long k;
        cin >> k;
        int it = lower_bound(a.begin(), a.end(), k) - a.begin();
        long long tmp = abs(a[it] - k);
        if (it > 0) tmp = min(tmp, abs(a[it-1] - k));
        res += tmp;
    }
    cout << res << endl;
}