Google KickStart 19 round A 题目解析

[TOC]

题目链接

A. Training

这题很简单,处理一下前缀和就完事儿,没什么好说的。

code

github

B. parcel

这题还是很有意思的.

题解可以参考官方题解

我这里就是将题解翻译一下,同时总结一下学到东西。

分析

首先对于每一个没有 deliver 的位置,我们可以先求出它的最短距离。这个可以将整个地图看成一个 graph,然后,任意两个deliver之间的距离为 0,然后将 所有deliver 看做图上的一个节点,其他的点与点之间的距离为 曼哈顿距离,那么只需要对图做一个 bfs 就行了,这就是answer中说的 muti-source bfs,其实感觉与bfs 并没有什么区别。

然后对于答案来说我们可以二分枚举,将优化问题转化为 满足性问题。

也就是说 对于一个固定的 $K$, 我们判断,是否可以找到一个点使得,所有点到delivers的距离不会超过 $K$.

判断这个是很容易的。

这里涉及到一个 曼哈顿距离切比雪夫距离 的转化

关于曼哈顿距离与切比雪夫距离的转化,推荐参考 SGColin's Space

有了这个我们就可以得到,答案分析中的结果

dist((x1, y1), (x2, y2)) = max(abs(x1 + y1 - (x2 + y2)), abs(x1 - y1 - (x2 - y2)))

那么固定一个点 ($x_2$,$y_2$) 我们只需要求出 $\min (x_i+y_i),\max (x_i+y_i),\min (x_i-y_i),\max (x_i - y_i), i \in dist(i)>K$

这个复杂度是 $O(RC)$ 的

加上二分的复杂度

$O(RClog(R+C))$

code

github

C. contention

这题非常有意思,官方给的编程实在太麻烦,太难懂了,毕竟一个笔试题又不是算法竞赛,居然搞出 interval tree 这种东西实在是太可怕了,正式赛只有两人做出来,我参考了第一人的做法Mahmoudian

分析

首先我们可以观察到,对于一个 booking 来说,如果它放在最后,那么它能确定的seat 数目一定是固定的,与前面 booking 的顺序无关。

同时我们 可以证明这样一个贪心的做法一定是正确的:

倒着确定booking 的顺序,每次取能booking 到的seat 最多的去掉,然后在剩余集合中如法炮制

伪代码

S : booking_set
for i =0 : q
    book_j = argmax(number_of_seat(S))
    S = S/{book_j}

可以证明这个做法一定是正确的。

证明

设这样做不是最优的,也就是说 存在一种顺序 $p_1 \dots p_q, numberOfSeat(p_q)<numberOfSeat(p_j)$ 比 $p_j$ 放在最后更优。我们总是可以将 $p_j$ 放在最后使得其不弱于序列$P_i$,即 构造顺序 $p_1,\dots ,p_{j-1},p_{j+1},\dots ,p_q,p_j$ 称为序列2

首先,

$ans1<=number1(p_q),ans2<=number2(p_j),number1(p_j)>=number2(p_j)>=number1(p_q)\ge ans1$ 因此 在序列 1中 $p_j$ 不是瓶颈。同时 $number2(p_i)\ge number1(p_i),\forall i\neq j$ (因为遮挡少了 $p_j$)

ok。这就引出了一个朴素的算法,就是伪代码的做法,不过我们需要确定的是booking 放在最后能够book到多少seat。 这个可以用扫描线 $O(Q)$ 做出来,只有 $Q$ 条线段。

这是我之前的code,只能过test 1

#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f
#define INF64 0x3f3f3f3f3f3f3f3f
#define ms(x,v) memset(x,(v),sizeof(x))

typedef long long LL;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TIII;
typedef pair<PII,int> PIII;
const int MAXN = 1e6+10;

int del(map<PII,int>& seg){
    int last = 0;
    for(auto it = seg.begin(); it != seg.end();){
        auto now = it;
        const int st = now -> first.first;
        const int ed = -now -> first.second;
        int& val = now ->second=0;
        if(ed <= last){
            ++it;
            continue;
        };
        if(last<st)last = st;
        auto jt = ++it;
        assert(now != it);


        assert(last < ed);
        assert(last >=st);
        int sweep_right = last;
        for(;jt != seg.end() ; ++jt){
            const int l = jt ->first.first;
            const int r = - jt ->first.second;
            if(sweep_right >=ed || l >= ed)break;
            if(r <= sweep_right)continue;
            if(l > sweep_right)val+= l - sweep_right;
            sweep_right = r;
        }
        if(sweep_right < ed) val += ed - sweep_right;

        // for next
        last = max(ed,last);
    }
    // del max one
    PIII p = *seg.begin();
    for(auto it :seg){
        if(it.second > p.second)p = it;
    }
    // cout << p.first.first << " " << p.first.second << " " << p.second<<"\n";
    seg.erase(p.first);
    return p.second;
}


int solve(){

    int n,q;
    cin >> n >> q;
    map<PII,int>seg;
    int ans =n+1;
    for(int i=0; i<q ; ++i){
        int l,r;
        cin >> l>>r;
        seg.insert({{--l,-r},0});
    }
    if(seg.size() < q)return 0;
    while(!seg.empty() && ans!=0){

        ans = min(ans,del(seg));
    }
    return ans;
}

int main(){

    ios :: sync_with_stdio(0);
    cin.tie(0);
    std::cout.precision(8);
    std::cout.setf( std::ios::fixed, std:: ios::floatfield );
    TIII t;
    int T;
    cin >> T;
    // cout << "T = " << T << "\n";
    for(int t =1 ; t <= T; ++t){
        auto ans = solve();
        cout << "Case #"<<t<<": "<<ans<<"\n";
    }
    return 0;
}

O(Qlog N) 版本

当然这样做无法通过大数据,这里我参考了 rank1 的做法,没有采用interval tree 的做法,而是用了二分。

和 $B$ 题一样,我们将问题转化为: 给定一个 $k$ 能否找到一种方式使得答案 大于等于 $k$。

参考上面的一些结论,很容易得到这样一个想法:

对于每一个 booking 来说,我们可以在满足能够让其book到的seat 大于等于 $k$ 的情况下将其尽可能的往后放。

具体可参见 code

code

github

reference

  1. 曼哈顿距离与切比雪夫距离转化证明
  2. muti-source-bfs

版权声明

本作品为作者原创文章,采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

作者: taotao

转载请保留此版权声明,并注明出处

© 著作权归作者所有
这个作品真棒,我要支持一下!
这里是个人google kickstart 2018,2019年题目解析,希望对渴望参加Google 招聘或者大厂...
0条评论
top Created with Sketch.