CF Round#424（div2）D题 二分+贪心

题意：

题目链接：http://codeforces.com/contest/831/problem/D
n个人，k把钥匙，一个门，每个人都需要拿到一把钥匙然后去开门，每走一个需要一个单位时间，一把钥匙只能给一个人用，问所有人都开门的最短时间是多少。

---

思路：

最大值最小化，二分。
对于判断函数，需要知道在限定的时间内是否所有人都能拿到钥匙开门。贪心思路，一开始想复杂了，认为求出每个人在限定时间内可以拿到的钥匙有哪些，按照能拿到钥匙较少的优先考虑，这样复杂度为O(n* n * logn * logn）
其实只需要将钥匙和人都排序，然后从左到右对每个人，遍历所有的钥匙，只要满足时间限制的钥匙就分给这个人，然后清除这个钥匙，结束钥匙的遍历，再访问下一个人，复杂度为O（n * n * logn）

---

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 2005;
const LL INF = 0x3f3f3f3f3f3f3f3f;

int n, k, p;
LL a[MAXN], b[MAXN];
set <int> :: iterator it;

bool vis[MAXN];

bool check(LL x) {
    int cnt = 0;
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            if (vis[j]) continue;
            if (abs(a[i] - b[j]) + abs(b[j] - p) <= x) {
                ++cnt; vis[j] = true;
                break;
            }
        }
    }
    if (cnt == n) return true;
    return false;
}


LL bin(LL l, LL r) {
    while (l < r) {
        LL mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return r;
}

int main() {
    //freopen("in.txt", "r", stdin);
    scanf("%d%d%d", &n, &k, &p);
    for (int i = 1; i <= n; i++)
        scanf("%I64d", &a[i]);
    for (int j = 1; j <= k; j++)
        scanf("%I64d", &b[j]);
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + k);
    printf("%I64d\n", bin(0, INF));
    return 0;
}