AOJ 0539 Pizza
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0539
解法
二分探索。
店の距離を小さい順にソートして宅配先がどこの店の間にあるかを二分探索して求める。
環状になっているので宅配先の距離が一番距離の大きい店より大きいなら、本店とどっちが近いか調べる。
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 100000; const int MAX_M = 10000; int x[MAX_N]; int solve(int low, int high, int p){ int ret; int mid = (low + high) / 2; if(low + 1 == high) return low; if(x[mid] <= p){ ret = solve(mid, high, p); }else{ ret = solve(low, mid, p); } return ret; } int main(){ x[0] = 0; int d, n, m; while(scanf("%d", &d) && d != 0){ scanf("%d %d", &n, &m); for(int i=1; i<n; i++) scanf("%d", x+i); sort(x, x+n); int ans = 0; for(int i=0; i<m; i++){ int p; scanf("%d", &p); if(x[n-1] <= p){ ans += min(p-x[n-1], d-p); }else{ int k = solve(0, n, p); ans += min(p-x[k], x[k+1] - p); } } printf("%d\n", ans); } return 0; }