aoj 0524 - Pizza

問題

問題概要

探索問題。２分探索で値の前後を求める。

解法

まず、storeに店の位置を入れる。この時、少しsample1を使って、考察してみる。本店の位置を0にしてしまうと、宅配先1からの距離は4-0=4で正確に求まるが、宅配先2からの距離は6-0=6で正確なものではなくなる。また、本店の位置を8にすると、絶対値を用いた距離を使えば行けそう。私は、0,8のどちらも入れる本店の位置として入れる形で考えました。
次に、大きなdに対して、どのように、宅配先の近くの店舗を見つけるか。bool store[]で配列を作り、storeの位置を記憶しておいてもいいが、dが大きくなると全て調べていては、TLEになってしまう。そこで、宅配先の前後の店舗の位置を調べるために２分探索を利用すれば良い。

ミス

特になし。

コード

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int main(void){
    while(1){
        int d, n, m; cin >> d;
        if(d == 0) return 0;
        cin >> n >> m;
        vector<int> store;
        rep(i, n - 1){
            int tmp; cin >> tmp;
            store.push_back(tmp);
        }
        store.push_back(0); store.push_back(d); //本店の位置を追加する
        sort(store.begin(), store.end());

        vector<int> k(m);
        rep(i, m) cin >> k[i];

        int sum = 0;
        rep(i, m){
            //２分探索でk[i]の前後の店舗の位置を見つける
            int l = *(lower_bound(store.begin(), store.end(), k[i]) - 1);
            int r = *(lower_bound(store.begin(), store.end(), k[i]));
            int ans = min(k[i] - l, r - k[i]);
            sum += ans;
        }
        printf("%d\n", sum);
    }
    return 0;
}