プロコン初心者日記

解いたプロコンの問題を保存しておくためのブログ

【AtCoder】AGC011 A. Airport Bus

AtCoderの問題

A: Airport Bus - AtCoder Grand Contest 011 | AtCoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ(初心者目線)

・考え方**

・実装**

・面白さ**

問題概要

・N人の人がバス停にTi時に来る
・それぞれの人はK以下の時間待てるがそれより待つことになると怒る
・バスの最大乗員人数はC人
・全員を怒らせないために必要なバスの台数の最小値は?
・バスが何時に来るかは任意に決められる(複数台同時でも良い)

方針

・あるバスに最初に乗った人が怒らないギリギリまで
・もしくは満員になるまで人を乗せる
・そしてまた新たに次のバスを用いる
・これの繰り返し

コード

焦って書いたコードなので汚いかもです!

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

int main(){
    int N;
    double C, K;
    cin >> N >> C >> K;
    vector<double> T(N, 0);
    FOR(i, 0, N) cin >> T[i];

    sort(T.begin(), T.end());
    int ans = 0;
    //先頭の人
    double t = T[0];
    int people = 0;
    bool last = false;
    FOR(i, 0, N){
        //バス出発
        if(t + K < T[i]){
            ans++;
            people = 1;
            t = T[i];
        }
        //乗れた
        else{
            people++;
            //あるバスで最後の乗客だった場合
            if(people==C){
                ans++;
                people = 0;
                if(i+1==N) last = true;
                //次の先頭の人
                t = T[i+1];
            }
        }
    }
    if(!last) ans++;
    cout << ans << endl;
}