Điểm trung chuyển xe buýt Cầu Giấy

Submit solution
Points: 2
Time limit: 1.0s
Memory limit: 100M
Author:
CNTT2_K59
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Điểm trung chuyển xe buýt Cầu Giấy là khu vực có lượng xe bus lưu thông cao và thường tập trung rất nhiều người – phần lớn là người đi xe bus, số còn lại là những người chạy xe ôm và bán hàng rong.

Mỗi ngày chuyến xe bus số 27 đưa rất nhiều sinh viên UTC từ Điểm trung chuyển Cầu Giấy đến Ký túc xá. Tổng công ty vận tải HanoiBus cần thống kê xem xe 27 nào đón nhiều khách nhất nên đã liên hệ 2 học sinh UTC là Hiếu và Hải. Nhưng họ chưa đi xe bus bao giờ, bạn hãy viết chương trình giải quyết vấn đề này giúp họ nhé!

Chuyến xe 27 đầu tiên trong ngày hoạt động vào lúc T, cứ sau thời gian D thì sẽ có chuyến xe bus khác cập bến và đón tất cả người đang đợi sau đó đi luôn. Nếu một người đến bến xe mà vừa đúng lúc xe cập bến thì người đó sẽ lên xe ấy, còn nếu không thì người đó sẽ đợi và lên xe tiếp theo.

Cho hai số T, D và dãy a chứa các số là thời điểm đến điểm dừng xe bus của n người. Hãy đưa ra số hiệu của xe bus chở nhiều người nhất, nếu có nhiều xe chở nhiều người nhất thì đưa ra số hiệu của xe nhỏ nhất.

Input:

Dòng đầu tiên chứa hai số T và D. (0 ≤ T, D ≤ \(10^9\))

Dòng thứ hai chứa số nguyên dương N (N ≤ \(10^5\)) là số thời điểm đứng đợi xe 27 của N người.

Dòng tiếp theo là N số nguyên chỉ thời điểm ra điểm đứng đợi xe lúc a[i] của mọi người. (0 ≤ a[i] ≤ \(10^9\))

Output:

Số hiệu của xe bus 27 chở nhiều khách nhất.

Example:

Input 1

3 5
4
3 4 10 6

Output 1

2

Giải thích:

Tại thời điểm t1 = 3, xe số hiệu thứ 1 đón một người khách đợi từ lúc a[0] = 3.

Tại thời điểm t2 = t1 + 5 = 8, xe số hiệu thứ 2 đón hai người khách đợi từ lúc a[1] = 4 và a[3] = 6.

Tại thời điểm t3 = t2 + 5 = 13, xe số hiệu thứ 3 đón một người khách đợi từ lúc a[2] = 10.

Xe số hiệu thứ 2 đón được hai người khách (a[1], a[3]).

Input 2

0 2
4
3 4 5 6

Output 2

3

Giải thích:

Tại thời điểm t = 0, xe số hiệu thứ 1 không đón người khách nào.

Tại thời điểm t = 2, xe số hiệu thứ 2 không đón người khách nào.

Tại thời điểm t = 4, xe số hiệu thứ 3 đón hai người khách đợi từ lúc a[0] = 3 và a[1] = 4.

Tại thời điểm t = 6, xe số hiệu thứ 4 đón hai người khách đợi từ lúc a[2] = 5 và a[3] = 6.

Xe số hiệu thứ 3 và xe số hiệu thứ 4 cùng đón được hai người khách nhưng xe có số hiệu nhỏ hơn là xe thứ 3.

Comments


  • 1
    CNTT2_K59  commented on Nov. 13, 2021, 2:51 p.m. ← edited

    Code tham khảo

    #include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int busStation(int t, int d, vector<int> a)
{
    sort(a.begin(), a.end(), greater<int>());
    int n, Max = 0, T = 0, count = 0, c = 1;
    while (a.size())
    {
        n = a.size();
        for (int i = 0; i < n; ++i)
        {
            if (a[i] <= t) count++;
        }
        if (Max < count) 
        {
            Max = count;
            T = c;
        }
        for (int i = 1; i <= count; ++i) a.pop_back();
        t += d; count = 0; c++;
    }
    return T;
}

int main() {
    int t, d, n, x;
    vector<int> a;

    cin >> t >> d >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> x;
        a.push_back(x);
    }

    cout << busStation(t, d, a);

    return 0;
}

  • 1
    cong_bien  commented on Nov. 5, 2021, 3:56 a.m.

    ai đó cho e xin code bài này để tham khảo được không ạ