ABC181E - Transfomable

前回ABCのEにトライしました。

各要素は難しくないのですが多数の配列の添え字を破綻なくまとめきるのには相当力が要ります。

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

int main(){
  int N,M;
  cin>>N>>M;
  vector<int> H(N);
  vector<int> W(M);
  for(int i=0;i<N;i++){
    cin>>H[i];
  }
  for(int i=0;i<M;i++){
    cin>>W[i];
  }  
  
  sort(H.begin(),H.end());
  
  int len=(N+1)/2;

  vector<int> LS(len);
  vector<int> RS(len);

  for(int i=0; i+1<N; i+=2) LS[i/2+1] = LS[i/2] + H[i+1] - H[i];
  for(int i=N-2; i>0; i-=2) RS[i/2] = RS[i/2+1] + H[i+1] - H[i];
  
  int minsum=10e10;
  int cur=0;
  for(int i=0;i<M;i++){
    cur=lower_bound(H.begin(),H.end(),W[i])-H.begin();
    if(cur%2==1) cur--;
    minsum=min(minsum,LS[cur/2]+RS[cur/2]+abs(H[cur]-W[i]));
  }
  cout<<minsum<<endl;
      
  return 0;
  
}