Google Kickstart 2019 Round A 题解

作者: jingy_ella | 来源:发表于2019-04-15 23:33 被阅读0次

1. Training

Problem：
从N个数中挑选P个数，使得这P个数增大为全部相同的数所需的代价最小
Solution：

暴力遍历所有的子数组，子数组的个数 $C_{n} ^p$ ，时间复杂度为 $O(n!)$
排序后只需考虑连续的 i, i + 1, ..., i + P - 1 子序列，子数组个数降为 N-P+1，直接计算每个子数组的和O(p)，总的时间复杂度 $O(n*p)$ ，使用滑动窗口计算每个子数组的和可优化至O(1)，总的时间复杂度 $O(n \lg n)$ ，大数据10^5可过。

int main() {
    int T;
    cin >> T;
    for (int t = 0; t < T; ++t) {
        int n, p;
        cin >> n >> p;
        vector<int> s;
        for (int i = 0; i < n; ++i) {
            int num;
            cin >> num;
            s.push_back(num);
        }
        sort(s.begin(), s.end());
        int len = n - p + 1;
        vector<long long> sum(len, 0);
        for (int i = 0; i < p; ++i) {
            sum[0] += s[I];
        }
        
        for (int i = 1; i < len; ++i) {
            sum[i] = sum[i - 1] - s[i - 1] + s[i + p - 1];
        }

        long long minn = 1e19;
        for (int j = 0; j < len; ++j) {
            long long tmp = s[j + p - 1] * p - sum[j];
            if (tmp < minn)
                minn = tmp;
        }
        cout << "Case #" << t+1 << ": " << minn << endl;
    }
}

2. Parcels

Problem：

对于给定的R*C的网格，1表示快递局，0表示待建位置，你可以在所有0的位置选择一个位置建立新的快递局，最短快递距离定义为各个点到距离最近的快递局的曼哈顿距离，输出所有点最短快递距离中的最大值

Solution：
最简单的暴力，按照题意模拟，使用bfs遍历记录每个点最近距离，再将所有待建位置依次设为新建快递局，再次对每个点进行bfs，更新所有点中最短快递距离的最大值，时间复杂度接近 $O((rc)^3)$ ，虽然写法比较丑陋，但对于大小仅为10的小数据依然能过。

```C++
#define ms(x,v) memset(x,(v),sizeof(x))

typedef pair<int, int> P;

const int maxn = 251;
int map[maxn][maxn];
int d[maxn][maxn];
int visit[maxn][maxn];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int r, c;

int bfs(int sx, int sy) {
    queue<P> que;
    que.push(P(sx, sy));
    ms(visit, -1);
    visit[sx][sy] = 0;
    while (que.size()) {
        P p = que.front();
        que.pop();
        if (map[p.first][p.second] == 1)
            return visit[p.first][p.second];
        for (int i = 0; i < 4; ++i) {
            int nx = p.first + dx[I];
            int ny = p.second + dy[i];
            if (nx >= 0 && nx < r && ny >= 0 && ny < c && visit[nx][ny] == -1) {
                que.push(P(nx, ny));
                visit[nx][ny] = visit[p.first][p.second] + 1;
            }
        }
    }
    return 0;
}

int main()
{
    std::ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t) {
        cin >> r >> c;
        string s;
        for (int i = 0; i < r; ++i) {
            cin >> s;
            for (int j = 0; j < c; ++j) {
                map[i][j] = s[j] - '0';
            }
        }
        ms(d, 0);
        int res = 0;
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                if (map[i][j] == 0) {
                    d[i][j] = bfs(i, j);
                    res = max(res, d[i][j]);
                }
            }
        }
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                if (!map[i][j]) {
                    ms(d, 0);
                    int tmp = 0;
                    map[i][j] = 1;

                    for (int k = 0; k < r; ++k) {
                        for (int l = 0; l < c; ++l) {
                            if (map[k][l] == 0) {
                                d[k][l] = bfs(k, l);
                                tmp = max(tmp, d[k][l]);
                            }
                        }
                    }
                    res = min(res, tmp);
                    map[i][j] = 0;
                }
            }
        }
        cout << "Case #" << t << ": " << res << endl;
    }
}
```

事实上，我们很容易想到一些对上述代码的优化：首先，观察最为丑陋的四层for循环，实际上在考虑将每个待建位置新建为快递局后，我们并不需要对整个网格再重新使用bfs遍历求每个点的最短快递距离，而只需要之前d[i][j]的值和当前点与新建快递局的曼哈顿距离进行比较取最小值即可，这样时间复杂度可以立即降低为 $O((rc)^2)$ 。

for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
        if (!map[i][j]) {
            int tmp = 0;
            for (int k = 0; k < r; ++k) {
                for (int l = 0; l < c; ++l) {
                    int newd = abs(k - i) + abs(l - j);
                    tmp = max(tmp, min(d[k][l], newd));
                }
            }
            res = min(res, tmp);
        }
    }
}

另一个可以优化的点是上述代码是从每个待建位置也就是值为0的点出发进行bfs遍历求到任一值为1的点的最短路径，最坏情况下需要进行r*c次bfs遍历，且每次遍历只能得到出发点的最短距离。而如果反向进行，从值为1的点出发进行bfs层次遍历，则可以通过一次遍历标记得到各层距离快递局的最短距离，即官方题解提到的多源bfs。

int bfs() {
    queue<P> que;
    ms(d, -1);
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (map[i][j] == 1) {
                d[i][j] = 0;
                que.push(P(i, j));
            }
        }
    }
    int res = 0;
    while (que.size()) {
        P p = que.front();
        que.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = p.first + dx[I];
            int ny = p.second + dy[i];
            if (nx >= 0 && nx < r && ny >= 0 && ny < c && d[nx][ny] == -1) {
                d[nx][ny] = d[p.first][p.second] + 1;
                que.push(P(nx, ny));
                res = max(res, d[nx][ny]);
            }
        }
    }
    return res;
}

使用上述优化后的时间复杂度 $O((rc)^2)$ 仍不能满足大数据250大小的时间限制，因此需要对四次for循环，也就是新建快递局后最短距离最大值的更新判断部分进行进一步优化。在最大化最小值或最小化最大值的问题中经常使用二分搜索来对假设解的可行性进行判断（例如POJ2456），本题如果我们将最优化问题转换为 判断是否能够新建一个快递局使最短快递距离的最大值小于等于k 的判定问题，则可以使用二分搜索将时间复杂度降低为 $O(rc \lg(r+c))$ 。

这样，我们只需要解决：对于一个固定的k，如何判断是否存在一个点可以作为新建位置使得原来到快递局的最短距离大于k的点到最新点的曼哈顿距离都不会超过k。距离某点曼哈顿距离等于k的点实际上是对角线为2k的菱形，如下图所示，因此我们只需要找出所有原来到快递局的最短距离大于k的点，再遍历所有点，找到一个其k-菱形可以包含上述所有点的点。为了便于计算，我们将坐标旋转45度（x->x+y, y->x-y），使其变为与坐标轴平行的正方形，即将曼哈顿距离转换为切比雪夫距离。

曼哈顿距离

bool check(int k) {
    int cnt = 0;
    // distance > k points min max x-axis & y-axis
    int minx = 1e9;
    int maxx = -1e9;
    int miny = 1e9;
    int maxy = -1e9;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (d[i][j] > k) {
                minx = min(minx, i + j);
                maxx = max(maxx, i + j);
                miny = min(miny, i - j);
                maxy = max(maxy, i - j);
                cnt++;
            }
        }
    }
    if (!cnt) {
        return true;
    }

    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (i + j - k <= minx && i + j + k >= maxx && i - j - k <= miny && i - j + k >= maxy) {
                return true;
            }
        }
    }
    return false;
}

最终代码：

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define ms(x,v) memset(x,(v),sizeof(x));

typedef pair<int, int> P;

const int maxn = 251;
int map[maxn][maxn];
int d[maxn][maxn];
int visit[maxn][maxn];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int r, c;

int bfs() {
    queue<P> que;
    ms(d, -1);
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (map[i][j] == 1) {
                d[i][j] = 0;
                que.push(P(i, j));
            }
        }
    }
    int res = 0;
    while (que.size()) {
        P p = que.front();
        que.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];
            if (nx >= 0 && nx < r && ny >= 0 && ny < c && d[nx][ny] == -1) {
                d[nx][ny] = d[p.first][p.second] + 1;
                que.push(P(nx, ny));
                res = max(res, d[nx][ny]);
            }
        }
    }
    return res;
}

bool check(int k) {
    int cnt = 0;
    // distance > k points min max x-axis & y-axis
    int minx = 1e9;
    int maxx = -1e9;
    int miny = 1e9;
    int maxy = -1e9;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (d[i][j] > k) {
                minx = min(minx, i + j);
                maxx = max(maxx, i + j);
                miny = min(miny, i - j);
                maxy = max(maxy, i - j);
                cnt++;
            }
        }
    }
    if (!cnt) {
        return true;
    }

    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (i + j - k <= minx && i + j + k >= maxx && i - j - k <= miny && i - j + k >= maxy) {
                return true;
            }
        }
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false); 
    cin.tie(0); 
    cout.tie(0);
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t) {
        cin >> r >> c;
        string s;
        for (int i = 0; i < r; ++i) {
            cin >> s;
            for (int j = 0; j < c; ++j) {
                map[i][j] = s[j] - '0';
            }
        }
        int res = bfs();
        
        int ll = -1;
        int rr = r + c;
        while (rr - ll > 1) {
            int mid = (rr + ll) >> 1;
            if (check(mid)) {
                rr = mid;
            }
            else {
                ll = mid;
            }
        }
        cout << "Case #" << t << ": " << rr << endl;
    }
}

3. Contention

Problem：
对于给定的N个座位和Q次请求，每次请求预订区间[L, R]座位的电影票，各请求间预订区间可能相交，后面的请求无法订到前面请求已预订的座位。通过调整各个预订请求间的次序，求使得每个请求都能满足至少预订k个座位的最大的k。

Solution：
本题同样是一个最大化最小值的问题，因此也可以考虑使用二分搜索来求解，问题转化为判定问题即 判断是否能够找到一种次序使得每个预订请求能够被预订的座位数都大于等于k。要满足这一k判定，我们直观的思路是将每个预订区间大于等于k的请求尽可能地往后放，范围越大的放的越后（每个请求只需要满足k个座位即可，放在前面占用多于k个座位浪费资源的可能性越大），然后从前往后判断是否能满足每个请求预定到k个位置？具体实现有待之后更新。

Google Kickstart 2019 Round A 题解

1. Training

2. Parcels

3. Contention

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读