Từ 1 tới 2 trên tổng số 2 kết quả

Đề tài: em làm xong nhưng ko biết sai ở đâu

  1. #1
    Ngày gia nhập
    12 2018
    Bài viết

    Mặc định em làm xong nhưng ko biết sai ở đâu

    Đề bài:

    B. Taxi drivers and Lyft
    time limit per test1 second
    memory limit per test256 megabytes
    inputstandard input
    outputstandard 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 m taxi drivers in the city, who every day transport the rest of the city residents — n riders.

    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 i the number ai — the number of riders that would call the i-th taxi driver when all drivers and riders are at their home?

    The taxi driver can neither transport himself nor other taxi drivers.

    The first line contains two integers n and m (1≤n,m≤105) — number of riders and taxi drivers.

    The second line contains n+m integers x1,x2,…,xn+m (1≤x1<x2<…<xn+m≤109), where xi is the coordinate where the i-th resident lives.

    The third line contains n+m integers t1,t2,…,tn+m (0≤ti≤1). If ti=1, then the i-th resident is a taxi driver, otherwise ti=0.

    It is guaranteed that the number of i such that ti=1 is equal to m.

    Print m integers a1,a2,…,am, where ai is the answer for the i-th taxi driver. The taxi driver has the number i if among all the taxi drivers he lives in the i-th smallest coordinate (see examples for better understanding).

    3 1
    1 2 3 10
    0 0 1 0
    3 2
    2 3 4 5 6
    1 0 0 0 1
    2 1
    1 4
    2 4 6 10 15
    1 1 1 1 0
    0 0 0 1
    In the first example, we have only one taxi driver, which means an order from any of n riders will go to him.

    In the second example, the first taxi driver lives at the point with the coordinate 2, and the second one lives at the point with the coordinate 6. Obviously, the nearest taxi driver to the rider who lives on the 3 coordinate is the first one, and to the rider who lives on the coordinate 5 is the second one. The rider who lives on the 4 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.


    #include <iostream>
    using namespace std;

    long long n,m,x[200000],t[200000],trai[200000],phai[200000],dem[200000];

    void vao()
    cin >> n >> m;
    int i;
    for (i=1;i<=n;i=i+1){cin >> x[i];};
    for (i=1;i<=n;i=i+1){cin >> t[i];};

    void tinh()
    int i;
    int tam;
    for (i=1;i<=n;i=i+1)
    if (t[i]==0) {trai[i]=tam;}
    else tam=i;
    for (i=n;i>=1;i=i-1)
    if (t[i]==0) {phai[i]=tam;}
    else tam=i;
    for (i=0;i<=n+1;i=i+1) {dem[i]=0;};
    long long d_trai,d_phai;
    for (i=1;i<=n;i=i+1)
    if (d_trai<=d_phai) {dem[trai[i]]=dem[trai[i]]+1;}
    else {dem[phai[i]]=dem[phai[i]]+1;}
    for (i=1;i<=n;i=i+1)
    if (t[i]==1) {cout << dem[i] << " ";};

    int main()

  2. #2
    Ngày gia nhập
    08 2017
    Bài viết

    Trích dẫn Nguyên bản được gửi bởi user4852 Xem bài viết
    Đề bài:
    B. Taxi drivers and Lyft ...
    không có chú thích, làm sao biết user hiểu thế nào, muốn làm chi để xác định đúng sai ?

    C++ Code:
    1. #include <iostream>
    2. using namespace std;
    4. long long n,m,x[200000],t[200000],trai[200000],phai[200000],dem[200000];
    6. void vao()
    7. {
    8.     cin >> n >> m;
    9.     n=n+m;
    10.     int i;
    11.     for (i=1;i<=n;i=i+1){cin >> x[i];};
    12.     for (i=1;i<=n;i=i+1){cin >> t[i];};
    13. }
    15. void tinh()
    16. {
    17.     int i;
    18.     int tam;
    19.     tam=0;
    20.     x[0]=-1000000009;
    21.     for (i=1;i<=n;i=i+1)
    22.     {
    23.         if (t[i]==0) {trai[i]=tam;}
    24.         else tam=i;
    25.     };
    26.     tam=n+1;
    27.     x[n+1]=1000000009;
    28.     for (i=n;i>=1;i=i-1)
    29.     {
    30.         if (t[i]==0) {phai[i]=tam;}
    31.         else tam=i;
    32.     };
    33.     for (i=0;i<=n+1;i=i+1) {dem[i]=0;};
    34.     long long d_trai,d_phai;
    35.     for (i=1;i<=n;i=i+1)
    36.     {
    37.         d_trai=x[i]-x[trai[i]];
    38.         d_phai=x[phai[i]]-x[i];
    39.         if (d_trai<=d_phai) {dem[trai[i]]=dem[trai[i]]+1;}
    40.         else {dem[phai[i]]=dem[phai[i]]+1;}
    41.     };
    42.     for (i=1;i<=n;i=i+1)
    43.     {
    44.         if (t[i]==1) {cout << dem[i] << " ";};
    45.     }
    46. }
    48. int main()
    49. {
    50.     vao();
    51.     tinh();
    52. }

Tags của đề tài này

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn