Codeforces Round #424 -(二分&贪心)||dp-D. Office Keys

http://codeforces.com/contest/831/my
给定n个人的位置，和k个钥匙，再给你办公室的位置。
每个人需要拿一个钥匙，然后到办公室，问你每个人都到达办公室的最短时间。
1 dp
dp[i][j]为前i个人，拿了前j个的最小值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2005;
ll a[maxn], b[maxn], n, k, p;
ll dp[maxn][maxn];

int main(void)
{
while(cin >> n >> k >> p)
    {
for(int i = 1; i <= n; i++)
scanf("%I64d", &a[i]);
for(int i = 1; i <= k; i++)
scanf("%I64d", &b[i]);
        sort(a+1, a+1+n);
        sort(b+1, b+1+k);
        dp[0][0] = 0;
for(int i = 1; i <= n; i++)
for(int j = i; j <= k; j++)
            {
if(i == j)
                    dp[i][j] = max(dp[i-1][j-1], abs(a[i]-b[j])+abs(b[j]-p));
else
                    dp[i][j] = min(dp[i][j-1], max(dp[i-1][j-1], abs(a[i]-b[j])+abs(b[j]-p)));
            }
printf("%I64d\n", dp[n][k]);
    }
return 0;
}

2 贪心。
我们发现，最远那个地方老是拖后腿，他需要把最远的钥匙给拿了，才能保证时间最短（如果别人拿需要更多时间。）
所以我们就贪心一个规律
排序后
每个人都从左边拿。
这样最远的肯定拿到最远的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=2005;
int m,n,p;
int a[maxn];
int b[maxn];
bool solve(ll x){
bool vis[maxn];
memset(vis,false,sizeof(vis));
int cnt=0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
    {  if(vis[j]) continue;
if(1ll*abs(a[i]-b[j])+1ll*abs(p-b[j])<x)
        {cnt++;
         vis[j]=true;
break;}
   }
if(cnt==m)
return true;
return false;
}
int check(long long x)
{
int i;
int now=0;
for(i=0;i<m;i++)
    {
while(abs(b[now]-a[i])+abs(p-b[now])>x)
        {
            now++;
if(now>=n)
return 0;
        }
        now++;
    }
return 1;
}
int main()
{   scanf("%d%d%d",&m,&n,&p);
for(int i=0;i<m;i++){
scanf("%d",&a[i]);
    }
    sort(a,a+m);
for(int i=0;i<n;i++){
scanf("%d",&b[i]);
    }
    sort(b,b+n);
    ll r=0x3f3f3f3f3f3f3f3f;
    ll l=0;
    ll ans=0;
while(l<=r){
        ll mid=(l+r)/2;
if(solve(mid)){
            ans=mid;
            r=mid-1;
        }
else
            l=mid+1;
    }
printf("%lld\n",ans-1);
return 0;
}