题解 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}

#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提供的latex渲染。