Office Keys

题目描述

There are $n$ people and $k$ keys on a straight line. Every person wants to get to the office which is located on the line as well. To do that, he needs to reach some point with a key, take the key and then go to the office. Once a key is taken by somebody, it couldn’t be taken by anybody else.

You are to determine the minimum time needed for all $n$ people to get to the office with keys. Assume that people move a unit distance per $1$ second. If two people reach a key at the same time, only one of them can take the key. A person can pass through a point with a key without taking it.

题意概述

在一条数轴上有$n$个人和$k$把钥匙。每个人一秒可以移动一个单位长度。已知办公室的位置在$p$，求所有人都拿到一把钥匙并到达办公室的最少时间。

数据范围：$1 \le n \le 1000, \ 1 \le k \le 2000, \ 1 \le p \le 10^9$。

算法分析 1

考虑贪心策略，一定有一组最优解中所有人选的钥匙在排序后是连续的。否则，可以将钥匙向靠近门的方向移动使它们连续，这不会使答案变劣。因此可以直接暴力枚举。

代码 1

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int n, k, p, ans = 2e9, a[1001], b[2001];
int get_dist(int x, int y) { return abs(a[x] - b[y]) + abs(b[y] - p); }
int main()
{
  cin >> n >> k >> p;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= k; ++i) cin >> b[i];
  sort(a + 1, a + n + 1), sort(b + 1, b + k + 1);
  for (int i = 1; i <= k - n + 1; ++i) {
    int ma = 0;
    for (int j = i; j <= i + n - 1; ++j) ma = max(ma, get_dist(j - i + 1, j));
    ans = min(ans, ma);
  }
  cout << ans << endl;
  return 0;
}

算法分析 2

令$f_{i, j}$表示前$i$个人拿前$j$把钥匙的最少时间，DP 解决问题。

代码 2

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n, k, p, a[1001], b[2001], f[1001][2001];
int get_dist(int x, int y) { return abs(a[x] - b[y]) + abs(b[y] - p); }
int main()
{
  cin >> n >> k >> p; memset(f, 0x7f, sizeof(f));
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= k; ++i) cin >> b[i];
  sort(a + 1, a + n + 1), sort(b + 1, b + k + 1);
  for (int i = 0; i <= k; ++i) f[0][i] = 0;
  for (int i = 1; i <= n; ++i)
    for (int j = i; j <= k; ++j)
      f[i][j] = min(f[i][j - 1], max(f[i - 1][j - 1], get_dist(i, j)));
  cout << f[n][k] << endl;
  return 0;
}