AtCoder Grand Contest 011 AGC011 A - Airport Bus

atcoder.jp

左端を固定して、条件を満たすように右に伸ばしていくのを貪欲に行う。実装は尺取り法が楽になる。

int main() {
    ll N, C, K;
    cin >> N >> C >> K;
    vector<ll> T(N);
    rep(i,N)cin >> T[i];
    sort(all(T));
    int r = 0;
    int ans = 0;
    for(int l = 0; l < N;){
        while(r+1 < N && r+1 - l + 1 <= C && T[r+1] <= T[l] + K){
            r++;
        }
        l = r+1;
        ans++;
    }
    cout << ans << endl;
}