题解 – [20231109NOIP模拟/CF830A] Office Keys

题目大意

在一条数轴上有 n 人 k 把钥匙，每个人能拿且仅能拿一把钥匙，办公室坐标为 p ，所有人同时开始去拿钥匙，然后去办公室。求所有人消耗的最大时长。

每人的坐标在 a_i ，每个钥匙的坐标在 b_i 。

题解

我们先将每个人的坐标和钥匙先排序，然后可以证明：

\forall a_i\leq a_j\ ,\ b_i\leq b_j

为什么呢，任意将两个人的位置交换（也就是某种排序之前可能的情况），他们的线路会交叉，这时候答案显然对两个人都是不利的，因为从钥匙到办公室的距离不变，而两个人所花费的距离一定增加。所以仅当每个人到钥匙的路线都不交叉，才是最小的代价。

现在来考虑 dp ，有了上面的结论，想必 \mathcal{O}(nk) 的 dp 很好做。

状态设计：

1.可以设 dp[i][j] 表示当前第 i 个人，考虑到 j 号钥匙的时候最小代价的最大时间。每次维护一个上一人的最小值，然后从现在这个人的匹配中找出一个小的，去与上一人的最小值比较更新。

dp[i][j] = max(min(dp[i – 1][j]), distance(i \to j \to p)), j \in [i – 1, k – n + i]

2.设 dp[i][j] 表示前 i 个人取到 j 把钥匙时的解。个人认为这个方法更好理解。

dp[i][j] = min(dp[i][j – 1], max(dp[i – 1][j – 1], distance(i \to j \to p))), j \in [i, k – n + i]

数据范围其实不用那么在意，毕竟前面那些数据也用不到，这题还是轻松过
注意边界
memset(dp, 0x3f, sizeof(dp));
memset(dp[0], 0, sizeof(dp[0]));

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const int N = 1e3 + 10;
const int K = 2e3 + 10;
ll dp[N][K];//前i个人取了j把钥匙
int n, k, p;
ll a[N], b[K];
//考虑dp
int main()
{
  scanf("%d%d%d", &n, &k, &p);
  for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  for(int i = 1; i <= k; i++) scanf("%lld", &b[i]);
  sort(a + 1, a + n + 1);//其实这里已经把他处理成一个贪心问题了
  sort(b + 1, b + k + 1);
  for(int i = 1; i <= n; i++) 
  for(int j = i; j <= k - n + i; j++) 
    if(i == j) dp[i][j] = max(dp[i - 1][j - 1], abs_sub(a[i], b[j]) + abs_sub(b[j], p));
    else dp[i][j] = min(dp[i][j - 1], max(dp[i - 1][j - 1], abs_sub(a[i], b[j]) + abs_sub(b[j], p)));
  printf("%lld\n", dp[n][k]);
  return 0;
}