Lyft Level 5 Challenge 2018

A---The King's Race

http://codeforces.com/contest/1075/problem/A

题意：

一个人在((1,1)), 一个人在((n,n)), 现在他们每次轮流走一步，问谁先到达((x,y))

思路：

每个人走到((x,y))的步数是可以直接求出的。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long LL;

LL n;
LL x, y;


int main()
{
    while(scanf("%I64d", &n) != EOF){
        scanf("%I64d%I64d", &x, &y);
        LL mvwhite, mvblack;
        mvwhite = x - 1 + y - 1;
        mvblack = n - x + n - y;

        if(mvwhite <= mvblack){
            printf("White
");
        }
        else{
            printf("Black
");
        }
    }
    return 0;
}

B---Taxi drivers and Lyft

http://codeforces.com/contest/1075/problem/B

题意：

一条线上有住户和出租车司机，给定他们家的横坐标和他们的身份。一个出租车司机会接到离他家最近的所有客人，如果两个出租车司机一样近，这个客人会给横坐标小的司机。现在问所有出租车司机的客人分别是多少。

思路：

从左到右找到每个住户左边最近的出租车司机，从右到左找到每个住户右边最近的出租车司机。

对每个住户判断一下他属于哪一个出租车司机。

//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stdio.h>
#include <vector>
#include <map>
#include <set>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long LL;

int n, m;
const int maxn = 2e5 + 5;
int house[maxn];
int taxi[maxn];
int lft[maxn], rig[maxn];
int cnt[maxn];

int main()
{
    while(scanf("%d%d", &n, &m) != EOF){
        for(int i = 0; i < n + m; i++){
            scanf("%d", &house[i]);
            cnt[i] = 0;
        }
        for(int i = 0; i < n + m; i++){
            scanf("%d", &taxi[i]);
        }

        int last = -1;
        for(int i = 0; i < n + m; i++){
            if(taxi[i]){
                last = i;
            }
            else{
                lft[i] = last;
            }
        }
        last = -1;
        for(int i = n + m - 1; i >= 0; i--){
            if(taxi[i]){
                last = i;
            }
            else{
                rig[i] = last;
            }
        }

        for(int i = 0; i < n + m; i++){
             if(!taxi[i]){
                //cout<<lft[i]<<" "<<rig[i]<<endl;
                if(lft[i] == -1){
                    cnt[rig[i]]++;
                }
                else if(rig[i] == -1){
                    cnt[lft[i]]++;
                }
                else{
                    if(house[i] - house[lft[i]] <= house[rig[i]] - house[i]){
                        cnt[lft[i]]++;
                    }
                    else{
                        cnt[rig[i]]++;
                    }
                }
             }
        }

        bool flag = false;
        for(int i = 0; i < n + m; i++){
            if(taxi[i]){
                if(flag)printf(" ");
                else{
                    flag = true;
                }
                printf("%d", cnt[i]);
            }
        }
        printf("
");
    }
    return 0;
}

C---The Tower is Going Home

http://codeforces.com/contest/1075/problem/C

题意：

在((1,1))位置有一个象棋子。现在他要走到行数是1e9的位子。整个棋盘大小是1e9 * 1e9.棋盘中有一些横线和竖线的墙，问最少删去多少条可以让他走到行数是1e9的地方。

思路：

首先我们可以发现水平的墙中，如果他不是从1开始的，这个水平的墙就是没有用的。就不用存了。

然后对水平的墙按照x2排序，对竖直的墙也排序。

每次我们枚举要删去的竖直的墙。如果(i)要删去，那么(1~i-1)肯定也要删去。

然后我们统计一下删去了前(i)面墙之后，横着的墙里面有多少个和后面的竖着的墙有交点，有交点的这些横着的墙也是要删去的。

因为每次从左到右遍历竖着的墙的时候，被删去的横着的墙数应该是减少的。所以只用存一个变量来记录就可以了，不用每次都循环去找。

//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stdio.h>
#include <vector>
#include <map>
#include <set>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long LL;

int n, m;
const int maxn = 1e5 + 5;
struct horizontal{
    int x1, x2, y;
}h_spell[maxn];
int tot;
int v_spell[maxn];

bool cmp_h(horizontal a, horizontal b)
{
    return a.x2 < b.x2;
}

int main()
{
    while(scanf("%d%d", &n, &m) != EOF){
        tot = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d", &v_spell[i]);
        }
        v_spell[n + 1] = 1e9;
        sort(v_spell + 1, v_spell + n + 2);

        for(int i = 0; i < m; i++){
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            if(a == 1){
                h_spell[++tot].x1 = a;
                h_spell[tot].x2 = b;
                h_spell[tot].y = c;
            }
        }
        sort(h_spell + 1, h_spell + tot + 1, cmp_h);

        int id_h = 0, ans = n + m, cnt = tot;
        for(int i = 1; i <= n + 2; i++){
            while(id_h < tot && h_spell[id_h + 1].x2 < v_spell[i]){
                id_h++;
                cnt--;
            }
            ans = min(ans, cnt + i - 1);
        }


        printf("%d
", ans);
    }
    return 0;
}