先生の身長を固定して考えて,\(h\) に追加しておく. このとき,ペアの作り方の最適解の一つは, ソートした \(h\) に対して先頭から貪欲に 2人ずつ組んでいく方法が挙げられる.
それが解ければ,あとは先生の身長を全探索すれば OK. 前もって \(h\) をソートしておくことと, \(h\) のペア達の累積和を前もって計算しておくことで, クエリ毎に \(O(log (h.size))\) で答えられる.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m ;
cin >> n >> m;
vll h(n); cinv(h);
vll w(m); cinv(w);
sort(all(h));
ll n2 = (n+1)/2;
vll s(n2+1), t(n2+1);
rep(i,n2){
ll x;
if(2*i+1 < h.size()) x = abs(h[2*i] - h[2*i+1]);
else x = h[2*i];
s[i+1] = s[i] + x;
}
for(ll i = n2-1; i >= 0; i--){
ll x;
if(2*i-1 >= 0) x = abs(h[2*i-1] - h[2*i]);
else x = h[2*i];
t[i] = t[i+1] + x;
}
ll ans = INFL;
rep(i,m){
auto it = lower_bound(all(h), w[i]);
ll j = it-h.begin();
ll x = 0;
assert(j/2 < s.size());
x += s[j/2];
assert(j/2+1 < t.size());
x += t[j/2+1];
if(j & 1) j ^= 1;
x += abs(w[i] - h[j]);
// if(j % 2) x += abs(w[i] - h[j-1]);
// else x += abs(w[i] - h[j]); // rem: h[j]
chmin(ans,x);
}
cout << ans << endl;
return 0;
}