codeforce 830A Office Keys-白红宇

codeforce 830A Office Keys

阅读量：5065 次

发布时间：2019-06-12

本文共 3389 字，大约阅读时间需要 11 分钟。

D. Office Keys

There are n people and k keys on a straight line. Every person wants to get to the office which is located on the line as well. To do that, he needs to reach some point with a key, take the key and then go to the office. Once a key is taken by somebody, it couldn't be taken by anybody else.

You are to determine the minimum time needed for all n people to get to the office with keys. Assume that people move a unit distance per 1 second. If two people reach a key at the same time, only one of them can take the key. A person can pass through a point with a key without taking it.

Input

The first line contains three integers n, k and p (1 ≤ n ≤ 1 000, n ≤ k ≤ 2 000, 1 ≤ p ≤ 10⁹) — the number of people, the number of keys and the office location.

The second line contains n distinct integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹) — positions in which people are located initially. The positions are given in arbitrary order.

The third line contains k distinct integers b₁, b₂, ..., b_k (1 ≤ b_j ≤ 10⁹) — positions of the keys. The positions are given in arbitrary order.

Note that there can't be more than one person or more than one key in the same point. A person and a key can be located in the same point.

Output

Print the minimum time (in seconds) needed for all n to reach the office with keys.

Examples

input

2 4 50 20 100 60 10 40 80

output

input

1 2 10 11 15 7

output

Note

In the first example the person located at point 20 should take the key located at point 40 and go with it to the office located at 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. He spends 50seconds. Thus, after 50 seconds everybody is in office with keys.

有n个人，和m把钥匙，人和钥匙在一条坐标轴上分布，知道这些人和钥匙的位置和终点位置，人要先拿到钥匙才能去终点，求能让每个人都到达终点的最短时间。

换尔言之，也就是求最慢的一个人到达终点的最短时间。

显然要先对他们的位置排序。

然后选择动态规划的方法，有两个变量，也就是用dp[i][j]，其中,i代表第i个人，j代表第j把钥匙。

显然dp[i][j]直接相关的上一个状态是dp[i-1][j-1]，代表在dp[i-1][j-1]的基础上，第i个人选了第j把钥匙。

此外这里有一个隐含条件，钥匙一定要比人多（i<=j)，所以是由人来选择钥匙，所以第i个人可以选择第j把后的任意一把钥匙，那么dp[i][j]又会与dp[i][j-1]相关。

那么有一个问题便是抢钥匙了，是否会出现抢钥匙的情况呢？

假设a1<a2（人）,b1<b2（钥匙），a1选择了b2，a2也选择了b2的情况是否出现？

如果不注意的话，确实会出错，布局中唯一会出现矛盾的情况如下b1,a1,b2,s,a2，其中s是终点，并且已经没有b2以后的钥匙了，那么对于两人，b2才是最优解。

为了解决这个问题，需要特判，所以在i==j时，第i个人有最优使用第j把钥匙的机会，所以a2可以强制选择b2。

代码如下：

#include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  using namespace std;const int MAX=2e3+10;const double eps=1e-6;#define INF 0x7fffffff#define ll long long#define FOR(i,a,b) for(i=a;i<=b;i++)#define ROF(i,a,b) for(i=b;i>=a;i--)#define mst(a) memset(a,0,sizeof(a))#define mstn(a,n) memset(a,n,sizeof(a))//struct num{double l,r;}a[MAX];//bool cmp(const num &x, const num &y){return x.r>y.r;}int dp[MAX][MAX];int main(){ int n,m,aim,i,j,a[MAX],b[MAX]; cin>>n>>m>>aim; FOR(i,1,n) cin>>a[i]; FOR(i,1,m) cin>>b[i]; sort(a+1,a+n+1); sort(b+1,b+m+1); mst(dp); FOR(i,1,n) FOR(j,i,m) { if(i==j) dp[i][j]=max(dp[i-1][j-1],abs(a[i]-b[j])+abs(b[j]-aim)); else dp[i][j]=min(dp[i][j-1],max(dp[i-1][j-1],abs(a[i]-b[j])+abs(b[j]-aim))); } cout<
                  
                   <

转载于:https://www.cnblogs.com/qq936584671/p/7246188.html

你可能感兴趣的文章