CF1075B Taxi drivers and Lyft

TRZ_2007

2021-04-30 14:21:21

Solution

**[题解 【CF1075B Taxi drivers and Lyft】](https://www.luogu.com.cn/problem/CF1075B)** # Solution 观察数据范围,发现 $\mathcal{O(nm)}$ 的算法是跑不过去的,也就是说我们不能通过枚举 $a_i$ 来解决问题。 发现所有的坐标都是单调的,而且对于每一个乘客来说,接她的车只会是在离她**最近的左边的一辆和离她最近的右边的一辆中选最小值**,所以可以通过二分来计算出这两辆车的坐标最后得到解,时间复杂度 $\mathcal{O(n\log m)}$。 ~~最后贴一下最优解代码。~~ # Code ```cpp #include <cstdio> #include <cctype> #include <algorithm> using namespace std; #define gc getchar inline int read() { int c = gc(), t = 1, n = 0; while(isspace(c)) { c = gc(); } if(c == '-') { t = -1, c = gc(); } while(isdigit(c)) { n = n * 10 + c - '0', c = gc(); } return n * t; } #undef gc const int N = 2e5 + 9; int a[N],b[N],p[N],d[N],ans[N]; int n,m,np,nd,id; int main() { n = read(); m = read(); for(int i = 1;i <= n + m;i++) a[i] = read(); for(int i = 1;i <= n + m;i++) b[i] = read(); for(int i = 1;i <= n + m;i++) { if(b[i] == 0) p[++np] = a[i]; else d[++nd] = a[i]; } sort(d + 1,d + m + 1); d[0] = -1e9; //注意,这里一定要设立极限值,不然有可能会有乘客上了 0 号黑车(逃 for(int i = 1;i <= n;i++) { if(p[i] >= d[m]) { ans[m]++; continue; } //都比最表最大的大了,那么只能有最后一辆车来接他 id = lower_bound(d + 1,d + m + 1,p[i]) - d; //否则计算第一个大于等于他的坐标的车(右边离他最近的) if(d[id] - p[i] >= p[i] - d[id - 1]) ++ans[id - 1]; else ++ans[id]; } for(int i = 1;i <= m;i++) printf("%d ",ans[i]); return 0; } ```