Google Kickstart 2019 A

Posted on | In

2019 Google Kickstart Round A Solution

A. Training

从N个学生中选出K个，每名学生的能力值$S_i$， 要求选出的P个学生能力值相同。可以通过1h训练提升1名学生的能力值加1，问最少的训练时间。 $N\leq 10^5$

按能力排序，尺取法选出K个学生就AC了。。。。没睡醒，代码有点乱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
int t,n,p;
long long dp[10010];
int main()
{
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++)
    {
        int maxn=0;
        memset(dp,0,sizeof(dp));
        scanf("%d%d",&n,&p);
        for(int i=1;i<=n;i++)
        {
            int temp;
            scanf("%d",&temp);
            dp[temp]++;
            maxn=max(maxn,temp);
        }
        int cnt=0,j=1;
        long long ans=1000000000,re=0;
        for(int i=1;i<=maxn;i++)
        {
            cnt+=dp[i];
            re=re+cnt-dp[i];
            if(cnt<p)
                continue;
            if(cnt==p)
            {
                ans=min(re,ans);
                continue;
            }
            while(j<=i)
            {
                cnt-=dp[j];
                if(cnt>p)
                {
                    re=re-dp[j]*(i-j);
                    j++;
                    continue;
                }
                if(cnt==p)
                {
                    re=re-dp[j]*(i-j);
                    ans=min(re,ans);
                    j++;
                    break;
                }
                if(cnt<p)
                {
                    re=re-(dp[j]-p+cnt)*(i-j);
                    ans=min(re,ans);
                    dp[j]=p-cnt;
                    cnt=p;
                    break;
                }
            }
        }
        printf("Case #%d: %I64d\n",tt,ans);
    }
    return 0;
}

B. Parcels

一个R*C的网格，已经存在一些办公室，现在再新建一个办公室。一个点的交付时间是到最近办公室的曼哈顿距离。总交付时间是所有点交付时间的最大值。求新建办公室以后，总交付时间最小是多少？

$1 \leq R,C\leq 250$

二分，二分总交付时间，判断当总交付时间位K时，是否存在解

确定总时间后，用BFS扫描一遍图，之后统计没到的点的x+y，以及x-y，维护所有交付时间大于K的点的x+y与x-y最大值与最小值，之后判断差值是否大于K，即是否可以通过建一个办公室来满足要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
using namespace std;
int t,n,p;
int used[300][300];
int xx[4]={1,0,-1,0};
int yy[4]={0,1,0,-1};
int r,c;
int ans=0,re;
struct node{
    int x,y,k;
};
node ma[90000];
int cnt=0;
bool f(int k)
{
    //cout<<k<<endl;
    queue<node> que;
    int sum=0;
    for(int i=0;i<cnt;i++)
    {
        ma[i].k=k;
        que.push(ma[i]);
        sum++;
        used[ma[i].x][ma[i].y]=1;
    }
    while(!que.empty())
    {
        node q=que.front();
        que.pop();
        for(int i=0;i<4;i++)
        {
            if(q.x+xx[i]<=r&&q.x+xx[i]>0&&q.y+yy[i]<=c&&q.y+yy[i]>0&&q.k>0&&used[q.x+xx[i]][q.y+yy[i]]==0)
            {
                node temp;
                temp.x=q.x+xx[i];
                temp.y=q.y+yy[i];
                temp.k=q.k-1;
                used[q.x+xx[i]][q.y+yy[i]]=1;
                sum=sum+1;
                que.push(temp);
            }
        }
    }
    if(sum==(r*c))
        return true;
    int maxadd=0,minadd=r+c+1,maxsub=-r-c-1,minsub=r+c+1;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
    {
        if(!used[i][j])
        {
            maxadd=max(maxadd,i+j);
            maxsub=max(maxsub,i-j);
            minadd=min(minadd,i+j);
            minsub=min(minsub,i-j);
        }
    }
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
        {
            if(abs(maxadd-(i+j))<=k&&abs(minadd-(i+j))<=k&&abs(maxsub-(i-j))<=k&&abs(minsub-(i-j))<=k)
                return true;
        }
    return false;
}
int main()
{
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++)
    {
        cnt=0;
        scanf("%d%d",&r,&c);
        for(int i=0;i<r;i++)
        {
            string temp;
            cin>>temp;
            for(int j=0;j<c;j++)
            {
                if(temp[j]=='1')
                {
                    ma[cnt].x=i+1;
                    ma[cnt].y=j+1;
                    ma[cnt].k=0;
                    cnt++;
                }
            }
        }
        int mink=0,maxk=r+c-1;
        while(mink<maxk)
        {
            memset(used,0,sizeof(used));
            int m=(mink+maxk)/2;
            if(f(m))
                maxk=m;
            else
                mink=m+1;
        }
        printf("Case #%d: %d\n",tt,mink);

    }
    return 0;
}

C. Contention

电影院有N个座位，从左到右标号1-N。有Q条预定，每条预定是一个范围$[L_i,R_i]$，这些预定可能存在重复，后面的预定系统只会分配区间内还没占用的座位。你一次只能向系统中输入一条预定，不过你可以改变预定顺序。问最大的K（每条预定都有K个座位被分配）是多少？$N\leq 10^6, Q\leq 30000$

有点懵逼。。。菜

orz。。。发现只有2个大佬过了，这波操作跪了跪了

可以发现第i个预定结果与前i-1个预定的顺序无关，那么我们可以从最后一个预定向前面递推，贪心的选取当前得到座位数最多的booking。

证明： 对于最优解 $q_1,q_2,…,q_i,..q_Q$,对应获得的座位数量为$ans_1,…,ans_Q$ ;如果存在一个booking $q_i$ 放在最后 获得seat $ans_Q’> ans_Q$, 那么可以得到序列$q_1,..,q_{i-1},q_{i+1},..q_Q,q_i$一定要优于最优解，与最优解矛盾。

所以可以用扫描线贪心选取最后预定获得seat最多的booking，时间复杂度为O(Q^2).

显然对于复杂度还是无法通过所有样例，官方说是用间隔树emmmmm。。。（这玩意是啥==），将N个座位切割成一个个不重叠的区间，这里用线段树来维护区间被几个booking预定了，每次取被一个booking覆盖的区间，更新覆盖目前这个booking获得的座位个数，然后将当前最多座位的booking删掉，相当于最后预定这个booking，其实就是把之前找最后一个booking的过程用线段树在logQ时间内完成了。

代码。。咕咕咕。。。