AT_yahoo_procon2017_final_b题解

· · 题解

写在前面

一道不错的题目，建议评橙~黄。

题目大意

给定 2 个大小分别为 N,M 的数组 X,Y，从这两个数组中分别选出 K 个数，求 \max\ (|X_1\ -\ Y_1|,\ |X_2\ -\ Y_2|,\ ...,\ |X_K\ -\ Y_K|\ ) 最小值。

题目分析

显然，本题可以二分答案：写一个 check 函数计算当最小值为 mid 时是否能找出 K 组 |X_i-Y_i| \leq d。

然后，就会有 2 组情况：

  1. 找不出 K 组：说明 mid 太小，令 left = mid + 1。

  2. 找的出 K 组：令 right = mid。

二分的思路清楚了，回顾一下二分模板，得到 while 的条件是 left<right，整个代码就基本上出来了。

AC代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool check(int d, int K, const vector<int>& A, const vector<int>& B) {
    int l = 0, r = 0;
    while (l < A.size() && r < B.size()) { //类似双指针的做法
        if (abs(A[l] - B[r]) <= d) {
            K--;
            l++;
            r++;
        } else if (A[l] > B[r]) {
            l++;
        } else {
            r++;
        }
    }
    return K <= 0;
}

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> A(N), B(M);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    for (int i = 0; i < M; ++i) {
        cin >> B[i];
    }
    sort(A.rbegin(), A.rend());
    sort(B.rbegin(), B.rend());

    int left = 0, right = 1e9;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (check(mid, K, A, B)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    cout << left << endl;
    return 0;
}