みんプロ2017 B - チーム決め

• 問題

問題概要

{a_i} (1 <= i <= N), {b_i} (1 <= i <= M)が与えられる.
各数列からK個選んで,昇順に並べた時のmax_(1 <= i <= K) (abs(a_i - b_i))を最小化せよ.
1 <= N,M,K <= 10⁵, 1 <= a_i,b_i <= 10⁹

解法

二分探索する. l = -1としないと X = 0とできる時に引っかかるので注意.
各探索では a[i] に対して a[i]-X <= b[j] <= a[i]+X を満たす最小のb[j]を貪欲に選んでいけば良い.
尺取り法を使えば O((N+M)log10⁹)

メモ

二分探索 -> 貪欲で選ぶと嘘っぽい？(嘘じゃない)
-> BITで数えられるやん！ -> MLEするわ...

絶対値の差がX以下のペアを選んで行く時,a[i]に対して条件を満たす最小のb[j]があり,
これ以外のb[j'] (昇順なのでj'>j)を選ぶとより多くのペアが作れると仮定する.
すると
b[j] を他の a[i'] (i'>i) に割り当てる -> 交差するので絶対値の差は大きくなる. a[i]-b[j],a[i']-b[j']の方が良い.
b[j] を割り当てない -> 単にa[i'] (i'>i)の選択肢が減るのでa[i]-b[j]の方が良い.
冷静に考えてみると明らか. 頭固い.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 100005;

int a[MAX_N],b[MAX_N];

int main(){
  int N,M,K; cin >> N >> M >> K;
  rep(i,N) scanf("%d",a+i);
  rep(i,M) scanf("%d",b+i);
  sort(a,a+N);
  sort(b,b+M);
  int l = -1, r = 1e9, mid;
  while(abs(r-l)>1){
    mid = (l+r)/2;
    int cnt = 0;
    for(int i=0,j=0;i<N&&j<M;i++){
      int lb = a[i] - mid, ub = a[i] + mid;
      while(j<M&&b[j]<lb) j++;
      if(b[j]<=ub) cnt++,j++;
    }
    if(cnt>=K) r = mid;
    else l = mid;
  }
  cout << r << endl;
  return 0;
}