AtCoder ABC 212 C - Min Difference (4Q, 灰色, 300 点)

いろんな解法がある。ここでは、ソートで解いてみよう！

• 問題へのリンク

問題概要

長さ の数列 と、長さ の数列 が与えられる。

各数列から要素 を選んだときの差 の最小値を求めよ。

制約

• 

考えたこと

本当にいろいろな解き方がある。その中でも易しいのは、 を全部混ぜてできる 個の値をソートしてしまう方法だと思われる。

そして、ソートした長さ の数列において、

---

から来た要素と、 から来た要素が隣接する部分についての、その差

---

のみを考えればよいのだ。

の計算量で解ける。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;
const int INF = 1 << 30;

int main() {
    int N, M, val;
    cin >> N >> M;
    vector<pint> v;
    for (int i = 0; i < N; i++) {
        cin >> val;
        v.emplace_back(val, 0);
    }
    for (int i = 0; i < M; i++) {
        cin >> val;
        v.emplace_back(val, 1);
    }
    sort(v.begin(), v.end());

    int res = INF;
    for (int i = 0; i+1 < v.size(); i++) {
        if (v[i].second != v[i+1].second) {
            res = min(res, v[i+1].first - v[i].first);
        }
    }
    cout << res << endl;
}