実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 366

問題概要

$1$ から $N$ までの番号が付けられた $N$ 個のおもちゃと、 $1$ から $N-1$ までの番号が付けられた $N-1$ 個の箱がある。おもちゃ $i \: (1\leq i\leq N)$ の大きさは $A_i$ 、箱 $i \: (1\leq i\leq N-1)$ の大きさは $B_i$ である。ここで、今から以下の操作を順に行うことを考える。

任意の正整数 $x$ を選んで、大きさ $x$ の箱を1つ購入する。
$N$ 個のおもちゃそれぞれを、元々あった箱と新しく購入した箱を合わせた $N$ 個の箱のいずれかに入れる。ただし、各おもちゃはそのおもちゃの大きさ以上の大きさを持つ箱にしか入れることはできず、1つの箱に2つ以上のおもちゃを入れることもできない。

このとき、操作2を実行できるような $x$ の値が存在するか判定し、存在するならばその最小値を求めよ。

制約

入力は全て整数。
$2\leq N \leq 2\times 10^5$
$1\leq A_i,B_i \leq 10^9$

考察

「ある条件を満たす $x$ の最小値」が聞かれているので、これは二分探索を使うことで求められそうだと反応できるかがポイント。実際、本問は「めぐる式二分探索」というものを使うことで比較的簡単に解くことができる。

めぐる式二分探索については以下の記事を参照のこと。

qiita.com

zenn.dev

以下では、「答えの候補となる $x$ が満たすべき条件」について考えていく。これは、以下のように書ける。

$N$ 個のおもちゃの大きさを格納した配列 $A$ と、新たに購入した大きさ $x$ の箱も加えた $N$ 個の箱の大きさを格納した配列 $B$ とを、それぞれ大きさが小さい順にソートする。このとき、すべての $i \: (1 \leq i \leq N)$ について、 $A_i \leq B_i$ が成り立つ。

厳密な証明については公式解説を参照してほしいが、これは貪欲的に考えても思いつくだろう (というかこの貪欲法をそのまま解法として用いることもできる) 。

ということで、二分探索の条件判定は、 $O(N)$ のループを使うことで実装できる。

以上をまとめたのが以下のコードになる。

コード

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

constexpr auto INF = 1e+9;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

bool check(vector<int> &A, vector<int> &B, int &new_box)
{
    vector<int> temp = B;
    temp.push_back(new_box);
    sort(all(temp));

    rep(i, 0, A.size())
    {
        if (A[i] > temp[i])
        {
            return false;
        }
    }

    return true;
}

int main()
{
    int N;
    cin >> N;
    vector<int> A(N), B(N - 1);
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N - 1) cin >> B[i];

    sort(all(A));

    int ng = 0, ok = INF;
    if (!check(A, B, ok))
    {
        cout << -1 << endl;
        return 0;
    }

    while (ok - ng > 1)
    {
        int mid = (ok + ng) / 2;
        if (check(A, B, mid))
        {
            ok = mid;
        }
        else
        {
            ng = mid;
        }
    }

    cout << ok << endl;
}