296. Best Meeting Point

给定由0和1组成的二维矩阵，在矩阵里找一个位置使得它离所有的1的曼哈顿距离（distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|）最小。这道题相当于在找针对曼哈顿距离的Geometric median。根据曼哈顿距离的定义，x和y可以分开找各自的最小，最后再相加。对于一维的A，B两点，当落在A和B内任意位置的曼哈顿距离和都一样，且都小于落在AB外的任意点。当拓展到更多点时，比如ABCD，同理落在BC间距离和都一样，且小于落在BC外。因此首尾两个指针同时往中心移动并累加它俩之间的距离就是一个维度的答案。对另一个纬度同理，最后两个纬度解相加是全局解。

题目和解法参考自这。

class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        const int M = grid.size(), N = M == 0 ? 0 : grid[0].size();
        vector<int> rows, cols;
        int res = 0;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] != 1) continue;
                rows.push_back(i);
                cols.push_back(j);
            }
        }
        sort(cols.begin(), cols.end());
        while (i < j) res += rows[j] - rows[i] + cols[j--] - cols[i++];
        return res;
    }
};