Submission #1156782

---

Source Code Expand

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

int main(void) {
    int n;
    int c;
    int k;
    std::vector<int> t;

    std::cin >> n;
    std::cin >> c;
    std::cin >> k;

    t.resize(n);
    for (int i = 0; i < n; i++) {
        std::cin >> t[i];
    }


    // greedy algorithm
    std::sort(t.begin(), t.end());

    int nbus = 0;
    int npassenger = 0;
    int end = -1;

    for (int i = 0; i < n; i++) {
        if (t[i] > end || npassenger > c) {
            nbus++;
            npassenger = 1;
            end = t[i] + k;
        } else {
            npassenger++;
        }
    }

    std::cout << nbus << std::endl;
}

Submission Info

Judge Result