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

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

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

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

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

AC代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 typedef long long LL;

 const int MAXN=;

 int n,k;

 int a[MAXN],b[MAXN],S;

 bool check(LL x){

     int p=;

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

         while(p<=k){

             p++;

             if(1LL*(abs(a[i]-b[p])+abs(b[p]-S))<=x) break;

         }

         if(p>k) return false;

     }

     return true;

 }

 int main()

 {

     scanf("%d %d %d", &n , &k, &S);

     for(int i=;i<=n;i++) scanf("%d", &a[i]);

     for(int i=;i<=k;i++) scanf("%d", &b[i]);

     sort(a+, a+n+);

     sort(b+, b+k+);

     LL l=,r=2e9+;

     LL mid;

     while(l<r){

         mid=(l+r)/;

         if(check(1LL*mid)) r=mid;

         else l=mid+;

     }

     printf("%d\n", l);

 }

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

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 typedef long long LL;

 const int INF=2e9+;

 const int MAXN=;

 int n,k;

 int a[MAXN],b[MAXN],S;

 int dp[MAXN][MAXN];

 int main(){

     scanf("%d %d %d", &n , &k, &S);

     for(int i=;i<=n;i++) scanf("%d", &a[i]);

     for(int i=;i<=k;i++) scanf("%d", &b[i]);

     sort(a+,a++n);

     sort(b+,b++k);

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

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

             dp[i][j] = INF;

     for(int i=; i<=k; i++) dp[][i]=;

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

         for(int j=i; j<=k; j++){

             dp[i][j] = min(dp[i][j-],max(dp[i-][j-],abs(a[i]-b[j])+abs(b[j]-S)));

         }

     printf("%d\n", dp[n][k]);

     return ;

 }

巴特西

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

最新文章

热门文章