题目链接:http://codeforces.com/contest/831/problem/D

题意:在一个一维坐标里,有n个人,k把钥匙(钥匙出现的位置不会重复并且对应位置只有一把钥匙),和一个终点p。问你每个人都拿到一把钥匙并且回到终点的情况下,n个人之中所花时间最长的那个人时间最少是多少?(一秒只能走一个单位的距离)

思路:考虑二分x,x为每个人能走的步数。对于两个人a,b和两把钥匙c,d 那么当p[a]<p[b]并且p[c]<p[d]时, a拿c钥匙,b拿d钥匙是最优的,因为对于p[c]到终点p的距离和p[d]到终点p的距离是固定的,但是如果a拿d, b拿c的话则出现交叉距离会更大,所花时间更大(贪心); 所以我们对于人和钥匙排个序,然后对于每个人都去拿在步数小于x的情况下(x包括从起点到拿钥匙,在从钥匙位置到终点的距离),最左边的那把钥匙。 然后预处理一下每个人拿每一个钥匙并且回到终点的时间即可。

import java.io.*;
import java.util.*; public class Main {
public static final int MAXN=1000+24;
public static final int MAXK=2000+24;
public static final int INF=((int)2e9)+24;
public static int n,k,p;
public static int[] pos=new int[MAXN];
public static int[] keys=new int[MAXK];
public static boolean[] vis=new boolean[MAXK];
public static int[][] dist=new int[MAXN][MAXK]; public static boolean check(int x){
Arrays.fill(vis, false);
for(int i=0;i<n;i++){
int keypos=-1;
for(int j=0;j<k;j++){
if(dist[i][j]<=x&&vis[j]==false){
keypos=j; break;
}
}
if(keypos==-1){
return false;
}
vis[keypos]=true;
}
return true;
} public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
PrintWriter out=new PrintWriter(System.out);
n=cin.nextInt(); k=cin.nextInt(); p=cin.nextInt();
for(int i=0;i<n;i++){
pos[i]=cin.nextInt();
}
for(int i=0;i<k;i++){
keys[i]=cin.nextInt();
}
Arrays.sort(pos,0,n);
Arrays.sort(keys,0,k);
for(int i=0;i<n;i++){
Arrays.fill(dist[i],0);
}
for(int i=0;i<n;i++){
for(int j=0;j<k;j++){
dist[i][j]=Math.abs(pos[i]-keys[j])+Math.abs(keys[j]-p);
// out.printf("%d ",dist[i][j]);
}
// out.println();
}
int l=0,r=INF,mid;
while(r>=l){
mid=l + ((r - l) >> 1);
if(check(mid)){
r=mid-1;
}else{
l=mid+1;
}
}
out.println(l);
out.flush(); out.close(); cin.close();
}
}
05-11 21:57