joi2009ho_b

宅配先に近い店舗を二分探索で見つける。

今回は探したいものが環状線になっているのでd-1と0をまたぐ必要がある

→番兵としてdの箇所にも店舗を置いておく(本店の座標は0=d)

あとはd[i] < kを満たすような最大のd[i]を見つけて、kを跨いだ隣の店舗d[i+1]との差分の小さい方が一番近い店舗となる。

#include<bits/stdc++.h>

using namespace std;

int d, n, m;

int a[100009];

int solve(int k){

int ok = 0;

int ng = n+1;

while(abs(ok-ng)>1){

int mid = (ok+ng)/2;

if(a[mid] <= k) ok = mid;

else ng = mid;

}

return min(abs(a[ok]-k), abs(a[ok+1]-k));

}

int main(){

cin >> d >> n >> m;

for(int i=1;i<n;i++) cin >> a[i]; a[0] = 0; a[n] = d;

sort(a, a+n);

int sum = 0;

for(int i=0;i<m;i++){

int k;

cin >> k;

sum += solve(k);

//cout << "solve:" << solve(k) << endl;

}

cout << sum << endl;

}