SquirrelSimulation [source code]

public class SquirrelSimulation {
static
/******************************************************************************/
public class Solution {
    public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
        int[] dist2tree = new int[nuts.length], dist2squir = new int[nuts.length];
        int maxDiff = Integer.MIN_VALUE, sum2tree = 0;
        for (int i = 0; i < nuts.length; i++) {
            dist2tree[i] = Math.abs(tree[0] - nuts[i][0]) + Math.abs(tree[1] - nuts[i][1]);
            sum2tree += dist2tree[i];
            dist2squir[i] = Math.abs(squirrel[0] - nuts[i][0]) + Math.abs(squirrel[1] - nuts[i][1]);
            int diff = dist2tree[i] - dist2squir[i];
            if (diff > maxDiff)
                maxDiff = diff;
        }
        return sum2tree * 2 - maxDiff;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SquirrelSimulation.Solution tester = new SquirrelSimulation.Solution();
    }
}

又是数学题, 又是一个最值搜索, 我不求你想到数学的做法, 先写一个简单的搜索办法出来好吧;

think how a human would do it; 这个题目不困难的一点在于, 你一次只能拿一个nut, 所以你每次拿到一个nut之后, 你就必须回城; 这个就让这个问题简化了很多;

画了一下图, 这个题目好像有思路; 果然还是做出来了, 最后的速度是15ms (59%);

总体的思路就是所有的比如n个nuts, 那么其中有一个是松鼠第一个去取的, 这个nut造成的距离就是松鼠和nut之间的距离加上nut到tree的距离. 其他的所有的n-1个nut对距离的贡献其实都是2 * nut到树的距离.

最后实际上你要选择的就是, 哪一个nut应该作为第一个nut, 让松鼠第一个去取. 换一个角度看, 这个被选中的第一个nut, 与其他的nut的区别就在于可以少贡献nut2tree - nut2squirrel的距离. 按照这个思路, 这个题目其实就很简单了;

所以middle的题目, 还是不要急着写代码, 题目看懂最重要, 用人逻辑想想这个问题整体到底是什么意思;

这个题目其实还给了一大把的hint, 不过其实一个也没看;

Take some example and make some observations.

这个是hint里面给出的一个建议, 很良心; 虽然有点笼统;

这个是discussion里面给出的一个解释:

Proof: Let the minimum distance from each nut to the tree be a_1, ..., a_n and let the minimum distance from each nut to the initial squirrel position be b_1, ..., b_n. Note that the minimum distance between two positions in the matrix is determined by their Manhattan distance.

Then, if the squirrel were to start at the tree, then the minimum total distance required to collect all the nuts is 2a_1 + ... + 2a_n. However, since the squirrel starts elsewhere, we just need to substitute one of the 2a_i terms with a_i + b_i. Or equivalently, we replace one of the a_i terms in the sum with b_i. To minimize the total sum value at the end, we choose i that maximizes a_i - b_i.

大概意思都差不多, 我感觉针对这个问题而言, 他这种思考方式不如我的; 不过这种无厘头假设的思路好像很常见了? 尤其是最值搜索的问题当中, 比如之前那个smallest permutation的问题也是这样, 还有个啥题好像也是这样; 我觉得更应该学习的是他们这种思考模式;

看了一下, discussion里面还有不少大神这个问题反而不会写; 感觉还是可能是举例总结和人逻辑的习惯不够;

discussion和editorial基本都是这个解法了, 没有其他的解法了.

Problem Description

There's a tree, a squirrel, and several nuts. Positions are represented by the cells in a 2D grid. Your goal is to find the minimal distance for the squirrel to collect all the nuts and put them under the tree one by one. The squirrel can only take at most one nut at one time and can move in four directions - up, down, left and right, to the adjacent cell. The distance is represented by the number of moves.

Example 1:
Input:
Height : 5
Width : 7
Tree position : [2,2]
Squirrel : [4,4]
Nuts : [[3,0], [2,5]]
Output: 12
Explanation:

Note:

1. All given positions won't overlap.
2. The squirrel can take at most one nut at one time.
3. The given positions of nuts have no order.
4. Height and width are positive integers. 3 <= height * width <= 10,000.
5. The given positions contain at least one nut, only one tree and one squirrel.

Difficulty:Medium
Total Accepted:2.3K
Total Submissions:4.4K
Contributor: fallcreek
Companies
square
Related Topics
math

Hint 1
Will Brute force solution works here? What will be its complexity?

Hint 2
Brute force definitely won't work here. Think of some simple solution. Take some example and make some observations.

Hint 3
Will order of nuts traversed by squirrel is important or only first nut traversed by squirrel is important?

Hint 4
Are there some paths which squirrel have to cover in any case? If yes, what are they?

Hint 5
Did you notice only first nut traversed by squirrel matters? Obviously squirrel will choose first nut which will result in minimum distance.