题解 【CF1075B Taxi drivers and Lyft】

Solution

观察数据范围，发现 $\mathcal{O(nm)}$ 的算法是跑不过去的，也就是说我们不能通过枚举 $a_i$ 来解决问题。
发现所有的坐标都是单调的，而且对于每一个乘客来说，接她的车只会是在离她最近的左边的一辆和离她最近的右边的一辆中选最小值，所以可以通过二分来计算出这两辆车的坐标最后得到解，时间复杂度 $\mathcal{O(n\log m)}$。
最后贴一下最优解代码。

Code

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