第８回日本情報オリンピック 本選 「ピザ」

顕著な二分探索。

なんかにぶたん使わなくても解けるらしいのですがややこしそうなので二分探索を使うほうがいいと思います。

#include <cstdio>
#include <algorithm>

using namespace std;

int nau;
int t[100003];

int main(){
  while(1){
  int d,n,m;
  scanf("%d",&d);
  if(d == 0)break;
  scanf("%d%d",&n,&m);
  t[0] = 0;
  for(int i = 1;i < n;i++){
    scanf("%d",&t[i]);
  }
  t[n] = d;
  
  sort(t,t + n + 1);
  
  int ans = 0;
  
  for(int i = 0;i < m;i++){
    scanf("%d",&nau);
    
    int lb = 0,ub = n;
    while(ub - lb > 1){
      int mid = (lb + ub) / 2;
      if(t[mid]>=nau) ub = mid;
      else lb = mid;
    }
    ans += min(abs(t[lb]-nau),abs(t[ub]-nau));
  }
  printf("%d\n",ans);
  }
  return 0;
}