题解 CF1075B 【Taxi drivers and Lyft】
_Cloud_
2020-10-26 22:09:05
###### 重新用latex渲染了一下
# 目前最快的方法
## 思路：
开两个数组，类似前缀和与后缀和 $(\text {sumf,sumb})$，一个记录前 $i$ 个节点到第 $i$ 节点最小距离的节点（前缀最优点），一个记录从 $n+m$ 到第 $i$ 节点的最小距离的节点（后缀最优点）。
遍历每一个 $i$，比较 $\text {sumf}$ 与 $\text {sumb}$ 大小即可。$\text {sumf}_0,\text {sumb}_{n+m+1}$附无穷大表示 $0$ 节点之前无司机和 $n+m+1$ 节点后无司机。
注意：因为最后输出的是数组，所以要在节点无穷大的地方特判。
### $\text {Code}$
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int sumf[N * 2], sumb[N * 2];
int ans[N * 2];
struct Node {
int z, s;
} a[N * 2];
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n + m; i++)
scanf("%d", &a[i].z);
for (int i = 1; i <= n + m; i++)
scanf("%d", &a[i].s);//按从小到大给的数据，不用sort
sumf[0] = sumb[n + m + 1] = 214748364;//无穷大表示没有司机
for (int i = 1; i <= n + m; i++) {//前缀最优
if (a[i].s == 1)
sumf[i] = i;
else
sumf[i] = sumf[i - 1];
}
for (int i = n + m; i >= 1; i--) {//后缀最优
if (a[i].s == 1)
sumb[i] = i;
else
sumb[i] = sumb[i + 1];
}
for (int i = 1; i <= n + m; i++) {
if (a[i].s == 0) {
if (sumf[i] == 214748364 && sumb[i] < 214748364) {//特判，不然会下标越界
ans[sumb[i]]++;
continue;
}
if ((sumb[i] == 214748364 && sumf[i] < 214748364)) {//同上
ans[sumf[i]]++;
continue;
}
if (a[i].z - a[sumf[i]].z <= a[sumb[i]].z - a[i].z) {
ans[sumf[i]]++;
} else {
ans[sumb[i]]++;
}
}
}
for (int i = 1; i <= n + m; i++) {
if (a[i].s == 1)//是司机就输出
printf("%d ", ans[i]);
}
return 0;
}
```
#### 评测结果：
PS：当然，这也只是目前最快的，原因是做的人不多。感谢@[做梦想Peach](https://www.luogu.com.cn/user/239030)提供的latex渲染。