D. Office Keys
time limit per test 2 seconds
memory limit per test 256 megabytes
There aren people and k keys on a straight line. Every person wants to get to theoffice which is located on the line as well. To do that, he needs to reach somepoint with a key, take the key and then go to the office. Once a key is takenby somebody, it couldn't be taken by anybody else.
You are to determine the minimum time needed for alln people to get to the office with keys.Assume that people move a unit distance per1 second. If two people reach a key atthe same time, only one of them can take the key. A person can pass through apoint with a key without taking it.
Input
The first line contains three integersn,k and p (1 ≤ n ≤ 1 000,n ≤ k ≤ 2 000,1 ≤ p ≤ 109) — the number of people,the number of keys and the office location.
The second line containsn distinct integers a1, a2, ..., an (1 ≤ ai ≤ 109) — positions in whichpeople are located initially. The positions are given in arbitrary order.
The third line containsk distinct integers b1, b2, ..., bk (1 ≤ bj ≤ 109) — positions of the keys.The positions are given in arbitrary order.
Note that there can't be more than one person or more than onekey in the same point. A person and a key can be located in the same point.
Output
Printthe minimum time (in seconds) needed for alln to reach the office with keys.
Examples
Input
2 4 50
20 100
60 10 40 80
Output
50
Input
1 2 10
11
15 7
Output
7
Note
In the first example the person located at point20 should take the key located at point 40 and go with it to the office locatedat point 50. He spends 30 seconds. The person located at point 100 can take the key located at point 80 and go to the office with it. Hespends 50seconds. Thus, after 50 seconds everybody is in office with keys.
【题意】在一条直线上，有n个人和k把钥匙，还有一个公司，问所有人都拿到一把钥匙(一个钥匙只能被拿一次)然后再到公司的最短时间是多少？
【思路1】由于要尽可能使每个人拿到距离自己最近的钥匙，我们先把所有人根据位置排序，把所有钥匙根据位置排序，然后二分答案，判断某一个值是否满足条件，具体判断过程见代码，每次尽量取左边的钥匙。
二分时注意使用long long 类型
#include <cstdio>
#include <map>
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)
typedef long long ll;
const int maxn= 2005;
const int mod = 20090717;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
int n,k,p;
ll a[maxn];
ll b[maxn];
bool vis[maxn];
bool judge(ll limit)
{
int num=0;
mst(vis,0);
for(int i=0;i<k;i++)
for(int j=0;j<n;j++)
{
if(vis[j]) continue;
if(abs(b[i]-a[j])+abs(b[i]-p)<=limit)
{
vis[j]=true;
num++;
break;
}
}
return num==n;
}
int main()
{
scanf("%d%d%d",&n,&k,&p);
for(int i=0;i<n;i++)
{
scanf("%I64d",&a[i]);
}
for(int i=0;i<k;i++)
{
scanf("%I64d",&b[i]);
}
sort(a,a+n);
sort(b,b+k);
ll l=0,r=2e9+5;
ll ans;
while(l<=r)
{
ll m=(l+r)/2;
if(judge(m))
{
r=m-1;
ans=m;
}
else l=m+1;
}
printf("%I64d\n",ans);
return 0;
}
【思路2】用dp[i][j]表示前i个人在前j把钥匙中都拿到了钥匙并到达公司的最短时间。(所有人最短时间里的最大值)
可以写出状态转移方程：
dp[i][j]=min(dp[i][j-1],max(dp[i-1][j-1]+abs(pos[j]-p)))
最终结果便是dp[n][k].
#include <cstdio>
#include <map>
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%I64d",&T);while(T--)
typedef long long ll;
const int maxn= 2005;
const int mod = 20090717;
const ll INF = 1e15;
const double eps = 1e-6;
int n,k;
ll p;
ll a[maxn];
ll b[maxn];
ll dp[maxn][maxn];
int main()
{
scanf("%d%d%I64d",&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);
mst(dp,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)); //由j>=i，故i==j时特判
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;
}