Codeforces 830A. Office Keys (贪心二分 or DP)

原题链接：http://codeforces.com/contest/830/problem/A

题意：在一条数轴上分别有n个人和k把钥匙(n<=k)，以及一个目的地，每个人要各自拿到一个钥匙后到达目的地。每个人的移动速度都是1，问所有人都到达目的地的最短时间。

思路：转化一下题意，就是求耗时最长的人所用的最短时间。

我们可以二分答案x，然后对排序后的人以及钥匙进行枚举，进行从左至右搭配。这里check函数中返回false的条件是从左至右所有人都能在x的时间内到达目的地，而计算这些人到达目的地的时间是：取最近的一对人与钥匙计算，为了每个人耗时最少（贪心），这是最优的。

AC代码：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<cmath>
 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<r){
32         mid=(l+r)/2;
33         if(check(1LL*mid)) r=mid;
34         else l=mid+1; 
35     }
36     printf("%d
", l);
37 }

这道题也可以用dp来做: dp[i][j]表示前i个人有前j个钥匙的最优解，利用01背包思想可以在O(n*k)时间内求出答案。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<cmath>
 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
", dp[n][k]);
28     return 0;
29 }