TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

Min Difference

問題

C – Min Difference
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

記録

解法

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 60;
const int INF = 1001001001;

// 二分探索
int binary_search(vector<int>& v, int x) {
  int l = -1;
  int r = v.size();

  while(1 < r - l) {
    int i = (l + r) / 2;
    if(x <= v[i]) {
      r = i;
    } else {
      l = i;
    }
  }

  return r;
}

int main() {
  int N, M;
  cin >> N >> M;

  vector<int> A(N);
  rep(i, N) { cin >> A[i]; }

  vector<int> B(M);
  rep(i, M) { cin >> B[i]; }

  int ans = INF;
  if(M <= N) {
    sort(B.begin(), B.end());
    rep(i, N) {
      int v = binary_search(B, A[i]);
      ans = min(ans, abs(A[i] - B[v]));
      if(v != 0) {
        ans = min(ans, abs(A[i] - B[v - 1]));
      }
    }
  } else {
    sort(A.begin(), A.end());
    rep(i, M) {
      int v = binary_search(A, B[i]);
      ans = min(ans, abs(B[i] - A[v]));
      if(v != 0) {
        ans = min(ans, abs(B[i] - A[v - 1]));
      }
    }
  }

  cout << ans << endl;
  return 0;
}