CodeForces 1075B

古城微笑少年丶 2022-04-24 16:34 163阅读 0赞

> 题目衔接：[http://codeforces.com/problemset/problem/1075/B][http_codeforces.com_problemset_problem_1075_B]

>  
> 
> Taxi drivers and Lyft
> 
> time limit per test
> 
> 1 second
> 
> memory limit per test
> 
> 256 megabytes
> 
> input
> 
> standard input
> 
> output
> 
> standard output
> 
> Palo Alto is an unusual city because it is an endless coordinate line. It is also known for the office of Lyft Level 5.
> 
> Lyft has become so popular so that it is now used by all mm taxi drivers in the city, who every day transport the rest of the city residents — nnriders.
> 
> Each resident (including taxi drivers) of Palo-Alto lives in its unique location (there is no such pair of residents that their coordinates are the same).
> 
> The Lyft system is very clever: when a rider calls a taxi, his call does not go to all taxi drivers, but only to the one that is the closest to that person. If there are multiple ones with the same distance, then to taxi driver with a smaller coordinate is selected.
> 
> But one morning the taxi drivers wondered: how many riders are there that would call the given taxi driver if they were the first to order a taxi on that day? In other words, you need to find for each taxi driver ii the number aiai — the number of riders that would call the ii-th taxi driver when all drivers and riders are at their home?
> 
> The taxi driver can neither transport himself nor other taxi drivers.
> 
> Input
> 
> The first line contains two integers nn and mm (1≤n,m≤1051≤n,m≤105) — number of riders and taxi drivers.
> 
> The second line contains n+mn+m integers x1,x2,…,xn+mx1,x2,…,xn+m (1≤x1<x2<…<xn+m≤1091≤x1<x2<…<xn+m≤109), where xixi is the coordinate where the ii-th resident lives.
> 
> The third line contains n+mn+m integers t1,t2,…,tn+mt1,t2,…,tn+m (0≤ti≤10≤ti≤1). If ti=1ti=1, then the ii-th resident is a taxi driver, otherwise ti=0ti=0.
> 
> It is guaranteed that the number of ii such that ti=1ti=1 is equal to mm.
> 
> Output
> 
> Print mm integers a1,a2,…,ama1,a2,…,am, where aiai is the answer for the ii-th taxi driver. The taxi driver has the number ii if among all the taxi drivers he lives in the ii-th smallest coordinate (see examples for better understanding).

>  
> 
> Examples
> 
> Input
> 
>     3 1
>     1 2 3 10
>     0 0 1 0
> 
> Output
> 
>     3
> 
> Input
> 
>     3 2
>     2 3 4 5 6
>     1 0 0 0 1
> 
> Output
> 
>     2 1
> 
> Input
> 
>     1 4
>     2 4 6 10 15
>     1 1 1 1 0
> 
> Output
> 
>     0 0 0 1
> 
> Note
> 
> In the first example, we have only one taxi driver, which means an order from any of nn riders will go to him.
> 
> In the second example, the first taxi driver lives at the point with the coordinate 22, and the second one lives at the point with the coordinate 66. Obviously, the nearest taxi driver to the rider who lives on the 33 coordinate is the first one, and to the rider who lives on the coordinate 55 is the second one. The rider who lives on the 44 coordinate has the same distance to the first and the second taxi drivers, but since the first taxi driver has a smaller coordinate, the call from this rider will go to the first taxi driver.
> 
> In the third example, we have one rider and the taxi driver nearest to him is the fourth one.

题目大意：给你一个街道上的n个人和m个司机，现在乘客会选择离他最近的那个司机，问你每个司机能载多少人，输入为n，m

表示乘客司机人数，接下来是n+m个坐标，表示每个人的坐标（假设是一条坐标轴），再下来n+m行是哪种人：0表示乘客，1表示司机。

思路：数据量很大，如果暴力肯定T，所以用二分查找，因为坐标是有序的，所以只需要找到该名乘客的前一名司机和后一名司机比较大小即可。这里用C++的lower\_bound()函数，返回的是第一个大于等于要查找的数的下标。

代码：

/*
    题目大意：n个出租车载m个人，第一行给你n个出租车司机和乘客的坐标，第二行给你这个人的身份
    乘客只会选择离他最近的1司机，如果距离相同则选坐标小的
    
    思路: 模拟，存下每个司机的位置，比较每个乘客与其距离
    
    
    */
    #include<map>
    #include<set>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include <vector>
    #include<cstring>
    #include<sstream>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll unsigned long long
    #define inf 0x3f3f3f
    #define esp 1e-8
    #define pp printf("\n");
    #define bug {printf("mmp\n");}
    #define mm(a,b) memset(a,b,sizeof(a))
    #define T() int test,q=1;scanf("%d",&test); while(test--)
    const int maxn=2e5+10;
    const double pi=acos(-1.0);
    const int N=201;
    const int mod=1e9+7;
    int a[maxn];
    int b[maxn];
    int dis[maxn];
    int c[maxn];
    int main()
    {
        int n,m;
        cin>>n>>m;
        for(int i=0;i<n+m ;i++)
        {
            cin>>dis[i];
        }
        int l1=0,l2=0;
        for(int i=0;i<m+n;i++)
        {
            int num;
            cin>>num ;
            if(num)
            {
                b[l1++]=dis[i];
            }
            else
                a[l2++]=dis[i];
        }
        for(int i=0;i<n;i++)
        {
            int judge=lower_bound(b,b+m,a[i])-b;
            if(judge==0)
                c[judge]++;
            else if(judge!=m&&a[i]-b[judge-1]>b[judge]-a[i])
                c[judge]++;
            else
                c[judge-1]++;
        }
        for(int i=0;i<m;i++)
            printf("%d ",c[i]);
        printf("\n");
        return 0;
    }

[http_codeforces.com_problemset_problem_1075_B]: http://codeforces.com/problemset/problem/1075/B