【AtCoder】AGC011 A. Airport Bus
AtCoderの問題
A: Airport Bus - AtCoder Grand Contest 011 | AtCoder
参考書
難しさ(初心者目線)
・考え方**
・実装**
・面白さ**
問題概要
・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; }