aoj 0524 - Pizza
問題概要
探索問題。2分探索で値の前後を求める。
解法
まず、storeに店の位置を入れる。この時、少しsample1を使って、考察してみる。本店の位置を0にしてしまうと、宅配先1からの距離は4-0=4で正確に求まるが、宅配先2からの距離は6-0=6で正確なものではなくなる。また、本店の位置を8にすると、絶対値を用いた距離を使えば行けそう。私は、0,8のどちらも入れる本店の位置として入れる形で考えました。
次に、大きなdに対して、どのように、宅配先の近くの店舗を見つけるか。bool store[]で配列を作り、storeの位置を記憶しておいてもいいが、dが大きくなると全て調べていては、TLEになってしまう。そこで、宅配先の前後の店舗の位置を調べるために2分探索を利用すれば良い。
ミス
特になし。
コード
#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){ //2分探索で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; }