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