打车公司一题求解# JobHunting - 待字闺中m*e2017-06-08 07:061 楼设计一个司机和乘客的mapping 系统,一个m*n的二维数组,有很多司机和乘客(乘客远多于司机),int【x,y]代表所处的坐标,任务是给设计算法,保证每个司机都拉到一个乘客,并且所有的pickup话费的路程和最小
o*r2017-06-08 07:062 楼二维比较难想,可以先想想一维的情况。这题也可能和二分图有关。我下班后试试。我擦,匈牙利算法早忘光光了,只记得dfs, 囧。。。class Location {Location(int x, int y) {this.x = x;this.y = y;}public int hashCode() {return x | y;}public boolean equals(Object obj) {if (obj == null) return false;else {if (obj instanceof Location) {Location l = (Location)obj;return l.x == x && l.y == y;} else {return false;} }}public int distance(Location location) {if (location == null) throw new IllegalArgumentException();return Math.abs(x - location.x) + Math.abs(y - location.y);}int x;int y;}class Pair {final Location left;final Location right;Pair(Location left, Location right) {this.left = left;this.right = right;}public int hashCode() {return left.hashCode() ^ right.hashCode();}public boolean equals(Object obj) {if (obj == null) return false;else {if (obj instanceof Pair) {Pair p = (Pair)obj;return p.left == left && p.right == right;} else {return false;}}}}public class Solution {public Map minCostPair(Set drivers, Set<Location> passengers) {if (drivers == null || passengers == null || drivers.size() == 0 ||drivers.size() > passengers.size())throw new IllegalArgumentException();minCost(drivers, passengers);return map;}private int minCost(Set drivers, Set passengers) {if (drivers.size() == 1) {Location d = drivers.iterator().next();int cost = Integer.MAX_VALUE;Location passenger = null;for (Location p : passengers) {if (d.distance(p) < cost) {cost = d.distance(p);passenger = p;}}Pair p = new Pair(d, passenger);map.put(p, cost);return cost;} else {Location d = drivers.iterator().next();drivers.remove(d);int cost = Integer.MAX_VALUE;for (Location p : passengers) {map.clear();Set tmp = new HashSet<>(passengers);tmp.remove(p);int c = d.distance(p) + minCost(drivers, tmp);if (c < cost) {cost = c;Pair pair = new Pair(d, p);map.put(pair, cost);}}return cost;}}private Map map = new HashMap<>();}
s*32017-06-08 07:063 楼保证每个司机都拉到一个乘客 乘客远多于司机 如果m*n是managable 的size 因该容易达成? 所以主要考察点事 所有的pickup话费的路程和最小?