Lyft Level 5 Challenge 2018 - Final Round (Open Div. 2)---ABC

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 -  + y - ;

         mvblack = n - x + n - y;

         if(mvwhite <= mvblack){

             printf("White\n");

         }

         else{

             printf("Black\n");

         }

     }

     return ;

 }

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 + ;

 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 = ; i < n + m; i++){

             scanf("%d", &house[i]);

             cnt[i] = ;

         }

         for(int i = ; i < n + m; i++){

             scanf("%d", &taxi[i]);

         }

         int last = -;

         for(int i = ; i < n + m; i++){

             if(taxi[i]){

                 last = i;

             }

             else{

                 lft[i] = last;

             }

         }

         last = -;

         for(int i = n + m - ; i >= ; i--){

             if(taxi[i]){

                 last = i;

             }

             else{

                 rig[i] = last;

             }

         }

         for(int i = ; i < n + m; i++){

              if(!taxi[i]){

                 //cout<<lft[i]<<" "<<rig[i]<<endl;

                 if(lft[i] == -){

                     cnt[rig[i]]++;

                 }

                 else if(rig[i] == -){

                     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 = ; i < n + m; i++){

             if(taxi[i]){

                 if(flag)printf(" ");

                 else{

                     flag = true;

                 }

                 printf("%d", cnt[i]);

             }

         }

         printf("\n");

     }

     return ;

 }

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 + ;

 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 = ;

         for(int i = ; i <= n; i++){

             scanf("%d", &v_spell[i]);

         }

         v_spell[n + ] = 1e9;

         sort(v_spell + , v_spell + n + );

         for(int i = ; i < m; i++){

             int a, b, c;

             scanf("%d%d%d", &a, &b, &c);

             if(a == ){

                 h_spell[++tot].x1 = a;

                 h_spell[tot].x2 = b;

                 h_spell[tot].y = c;

             }

         }

         sort(h_spell + , h_spell + tot + , cmp_h);

         int id_h = , ans = n + m, cnt = tot;

         for(int i = ; i <= n + ; i++){

             while(id_h < tot && h_spell[id_h + ].x2 < v_spell[i]){

                 id_h++;

                 cnt--;

             }

             ans = min(ans, cnt + i - );

         }

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 2)---ABC

最新文章

热门文章