AGC011 A AirportBus メモ[python]

1 min read読了の目安(約600字

問題概要

N人の人がそれぞれTi 時刻に空港に到着する
それぞれの待ち時間がK 以下になるようにピックアップのバスを用意する必要がある。
1つのバスにはC 人まで乗ることができるときバスは何個必要か

考察

  • C人の人がたまるか、先頭の人がK待つことになるかまで貪欲に考えていけば良い
    • Ti をソートして前から処理する
    • 現在空港にいる先頭の人の時刻、次に処理する人にidx,現在の乗客の人数を変数として持つ

実装方針

  • while を使って全体を見るようにする

提出コード

n, c, k = map(int, input().split())
t = [int(input()) for _ in range(n)]
t.sort()
ans = 1
lead_time = t[0]
idx = 1
num_passenger = 1
while idx < n:
    if lead_time + k < t[idx] or num_passenger + 1 > c:
        lead_time = t[idx]
        num_passenger = 1
        ans += 1
    else:
        num_passenger += 1
    idx += 1

print(ans)

メモ

  • 最初 num_passenger + 1 > cnum_passenger > c
    にしていてバグらせた。注意