Submission #2097336


Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://agc011.contest.atcoder.jp/tasks/agc011_a>
問題文============================================================
 高橋空港には,毎日飛行機で N 人の乗客が到着します. i 番目の乗客は時刻 Ti に到着します.
 
 高橋空港に到着する乗客は全員バスで市内へ移動します.
 どのバスも定員は C 人であり,C 人以下の乗客を乗せることができます.
 飛行機の乗客は,飛行機の到着時刻よりも早く出発するバスには乗ることができません.
 また,飛行機の到着時刻から K の時間が経過した後にもバスに乗れていないと,怒り出してしまいます.
 そのため,i 番目の乗客は,出発時刻が Ti 以上 Ti+K 以下であるようなバスに乗れるようにしないといけません.
 
 この条件のもとで,うまくバスの出発時刻を定めるとき,必要なバスの数の最小値を求めてください.
 ただし,バスの出発時刻は必ずしも整数である必要はなく,同じ時刻に出発するバスが複数あってもかまいません.
=================================================================

解説=============================================================

 乗客を時間に関してソートして、
 順番に、定員or時間に関して条件に反しない限りバスに乗せていけば良い
 
================================================================
*/
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    ll N,C,K; cin >> N >> C >> K;
    vector<ll> T(N);
    for(auto &in:T) cin >> in;
    sort(T.begin(),T.end());
    ll ans = 1;
    ll c = 0;
    ll from = 0;
    for(int i = 0; i < N;i++){
        if(c == C){
            ans++;
            c = from = 0;
        }
        
        if(c == 0){
            c++;
            from = T[i];
        }else{
            if(T[i] - from<=K){
                c++;
            }else{
                ans++;
                c = 1;
                from = T[i];
            }
        }
    }
    cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task A - Airport Bus
User vjudge4
Language C++14 (GCC 5.4.1)
Score 300
Code Size 2303 Byte
Status AC
Exec Time 17 ms
Memory 1024 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 2
AC × 12
Set Name Test Cases
Sample sample1.txt, sample2.txt
All sample1.txt, sample2.txt, in1.txt, in2.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, sample1.txt, sample2.txt
Case Name Status Exec Time Memory
in1.txt AC 1 ms 256 KB
in2.txt AC 17 ms 1024 KB
in3.txt AC 17 ms 1024 KB
in4.txt AC 17 ms 1024 KB
in5.txt AC 1 ms 256 KB
in6.txt AC 17 ms 1024 KB
in7.txt AC 15 ms 896 KB
in8.txt AC 17 ms 1024 KB
sample1.txt AC 1 ms 256 KB
sample2.txt AC 1 ms 256 KB