原题链接：
题意：在一条数轴上分别有n个人和k把钥匙(n<=k)，以及一个目的地，每个人要各自拿到一个钥匙后到达目的地。每个人的移动速度都是1， 问所有人都到达目的地的最短时间。
思路：转化一下题意，就是求耗时最长的人所用的最短时间。
我们可以二分答案x，然后对排序后的人以及钥匙进行枚举，进行从左至右搭配。 这里check函数中返回false的条件是从左至右所有人都能在x的时间内到达目的地，而计算这些人到达目的地的时间是：取最近的一对人与钥匙计算，为了每个人耗时最少（贪心），这是最优的。
AC代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 typedef long long LL; 8 const int MAXN=2005; 9 int n,k;10 int a[MAXN],b[MAXN],S;11 bool check(LL x){12 int p=0;13 for(int i=1;i<=n;i++){14 while(p<=k){15 p++;16 if(1LL*(abs(a[i]-b[p])+abs(b[p]-S))<=x) break;17 }18 if(p>k) return false;19 }20 return true;21 }22 int main()23 {24 scanf("%d %d %d", &n , &k, &S);25 for(int i=1;i<=n;i++) scanf("%d", &a[i]);26 for(int i=1;i<=k;i++) scanf("%d", &b[i]);27 sort(a+1, a+n+1);28 sort(b+1, b+k+1);29 LL l=0,r=2e9+5;30 LL mid;31 while(l
这道题也可以用dp来做: dp[i][j]表示前i个人有前j个钥匙的最优解，利用01背包思想可以在O(n*k)时间内求出答案。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 typedef long long LL; 8 const int INF=2e9+10; 9 const int MAXN=2005;10 int n,k;11 int a[MAXN],b[MAXN],S;12 int dp[MAXN][MAXN];13 int main(){14 scanf("%d %d %d", &n , &k, &S);15 for(int i=1;i<=n;i++) scanf("%d", &a[i]);16 for(int i=1;i<=k;i++) scanf("%d", &b[i]);17 sort(a+1,a+1+n);18 sort(b+1,b+1+k);19 for(int i=0; i<=n; i++)20 for(int j=0; j<=k; j++)21 dp[i][j] = INF;22 for(int i=0; i<=k; i++) dp[0][i]=0;23 for(int i=1; i<=n; i++)24 for(int j=i; j<=k; j++){25 dp[i][j] = min(dp[i][j-1],max(dp[i-1][j-1],abs(a[i]-b[j])+abs(b[j]-S)));26 }27 printf("%d\n", dp[n][k]);28 return 0;29 }