最佳会面地点

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated usingManhattan Distance, where distance(p1, p2) =|p2.x - p1.x| + |p2.y - p1.y|.

For example, given three people living at(0,0),(0,4), and(2,2):

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point(0,2)is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

Hint:

  1. Try to solve it in one dimension first. How can this solution apply to the two dimension case?
int minTotalDistance(vector<vector<int>>& grid) {
    // 分维度考虑，在某个维度让各点相遇的路程
    if (grid.empty()) return 0;
    const int R = grid.size(), C = grid[0].size();
    vector<int> rows, cols;
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (grid[r][c]) {
                rows.push_back(r);
                cols.push_back(c);
            }
        }
    }
    return minDist(rows) + minDist(cols);
}

int minDist(vector<int> &v) {
    int ans = 0;
    sort(v.begin(), v.end());
    int i = 0, j = (int)v.size() - 1;
    while (i < j) {
        ans += v[j--] - v[i++];
    }
    return ans;
}

令牌袋得分

int bagOfTokensScore(vector<int>& tokens, int P) {
    // token有两种用法：-tokens[i]、+1分，+tokens[i]、-1分
    // 贪心法，尽量多加分少减分，让单位token加分最多减分最少。
    // 加分时用最小的tokens[i]、减分时用最大的tokens[i]
    sort(tokens.begin(), tokens.end());
    int i = 0, j = (int)tokens.size() - 1;
    int point = 0, ans = 0;
    while (i <= j) {
        if (P >= tokens[i]) {
            P -= tokens[i++];
            ans = max(ans, ++point);
        } else if (point > 0) {
            P += tokens[j--];
            point--;
        } else {
            break;
        }
    }
    return ans;
}