第８回日本情報オリンピック 本選（オンライン） B ピザ

問題

第８回日本情報オリンピック 本選（2009 オンライン）　B ピザ

https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf#page=4

JOI難易度６を進めています。だいぶ難しい問題が増えてきました。
この問題はなんとか自力ACできました。

検討

円周上にある店舗のうち宅配先との距離が最小のものとの距離を加算していきます。
総円周が10e9、宅配先が10e5あるのでまともに全探索していては間に合わず、二分探索lower_boundを使いました。

イテレーターの使い方にはまだ慣れておらず、いちいちテンプレートを参照しながらやっています。
イテレーターから配列番号に引き直す際にitr-P.begin()でできるけれどそのまま[　]に突っ込むとエラーになることもあり，まだまだこのあたり試行錯誤しながらやってます。

lower_boundで宅配先以上の位置の店舗を確認し、その一つ手前の店舗と距離を比較しました。

円周なので原点を回るパターンも考えられるため原点との比較も入れました。
無駄だったかなと思って省いたコードを出したらWAしたので正しい方針でした。

提出コード

#include <bits/stdc++.h>
using namespace std;

int main(){
  int d,n,m;
  cin>>d>>n>>m;
  //店舗位置入力
  vector<int>P(n);
  P[0]=0;
  for(int i=1;i<n;i++){
    cin>>P[i];
  }
  sort(P.begin(),P.end());
  //宅配先入力
  int temp=0;
  int ans=0;
  int dif;
  for(int i=0;i<m;i++){
    cin>>temp;
    //tempに一番近い店舗を捜し距離を加算する
    auto itr=lower_bound(P.begin(),P.end(),temp);
    int a=itr-P.begin();
    //tempより大きな位置の店舗，小さな位置の店舗，原点を比較
    dif=min(min(abs(P[(a-1)%d]-temp),d-temp),abs(P[a]-temp));
    ans+=dif; 
  }
  cout<<ans<<endl;
  return 0;
}