CF-831D Office Keys 思维题

http://codeforces.com/contest/831/problem/D

题目大意是在一条坐标轴上，给出n个人，k把钥匙(k>=n)以及终点的坐标，所有人都可以同时运动，但不可以公用钥匙（相当于钥匙是消耗品，可以赋予人进入终点的能力），问最少花费多少时间可以让所有人都到达终点。

分析题意问题不大，无非就是每个方案中每个人的时间求最大值，每个方案再求最小值。但是如何在n^2的复杂度下枚举方案并计算耗时？这题的关键就是，可以证明，最优的方案一定是坐标值排序后连续的钥匙段（n把钥匙）顺序匹配排序后的n个人。所以对两者按坐标排序，将长度为n的窗口在key数组中滑动，按题意求解即可。

#include <iostream>

#include <cstring>

#include <string>

#include <queue>

#include <vector>

#include <set>

#include <stack>

#include <cmath>

#include <cstdio>

#include <map>

#include <algorithm>

#define LL long long

using namespace std;

const LL N = ;

LL n, m, p;

LL kp[N], np[N];

int main() {

    cin.sync_with_stdio(false);

    while (cin >> n >> m >> p)

    {

        for (int i = ; i < n; i++)

            cin >> np[i];

        for (int i = ; i < m; i++)

            cin >> kp[i];

        sort(np, np + n);

        sort(kp, kp + m);

        LL ans = 9999999999999LL;

        for (int i = ; i + n <= m; i++)

        {

            LL mx = ;

            for (int j = ; j < n; j++)

            {

                mx = max(mx, abs(kp[i + j] - np[j]) + abs(p - kp[i + j]));

            }

            ans = min(ans, mx);

        }

        cout << ans << endl;

    }

    return ;

}