JOI本選過去問 第8回 日本情報オリンピック本選 2問目 ピザ

問題文はこちら。

• 瞬殺問題。

• 二分探索地味に初めてでした。

• 一発ACはたのしい。

#include <cstdio>
#include <algorithm>
#include <vector>


using namespace std;


int main(){

  while(1){

long int d = 0;

long int n = 0;

int m = 0;

long int ans = 0;




  vector<long> dat;
  vector<long>::iterator it;


 dat.push_back(0);

 scanf("%ld",&d);

 if(d == 0) break;

  scanf("%ld%d",&n,&m);

  dat.push_back(d);

  for(long i = 1;i < n;i++){
    long tmp = 0;
    scanf("%ld",&tmp);
    dat.push_back(tmp);
  }

  sort(dat.begin(),dat.end());


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

    scanf("%ld",&tmp);

    it = lower_bound(dat.begin(),dat.end(),tmp);

    long s1 = 0,s2 = 0;


    s1= *it;

    --it;

    s2 = *it;

    ans += min(abs(tmp-s1),abs(tmp-s2));

  }

  printf("%ld\n",ans);

}

  return 0;

}