AT_agc011_a.[AGC011A] Airport Bus

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥机场每天有 $N$ 名乘客乘坐飞机抵达。第 $i$ 位乘客在时刻 $T_i$ 到达。

所有抵达高桥机场的乘客都需乘坐巴士前往市区。每辆巴士最多可载 $C$ 名乘客，也可以载更少。乘客不可以乘坐在他们到达机场之前就已经发车的巴士。此外，如果某位乘客在到达机场后的 $K$ 单位时间内还没有乘上巴士，他们就会生气。因此，第 $i$ 位乘客只能乘坐出发时间在 $T_i$ 以上且不超过 $T_i + K$ 的巴士。

在上述条件下，如果合理安排巴士的出发时刻，所需的最小巴士数是多少？巴士的出发时间不一定为整数，同一时刻可以有多辆巴士同时出发。

输入格式

输入按以下格式从标准输入读入：

$N$ $C$ $K$ $T_1$ $T_2$ $:\;T_N$

输出格式

输出所需的巴士数量的最小值。

输入输出样例

输入#1
```
5 3 5
1
2
3
6
12
```
输出#1
```
3
```
输入#2
```
6 3 3
7
6
2
8
10
6
```
输出#2
```
3
```

说明/提示

限制

$2 \leq N \leq 100000$
$1 \leq C \leq 10^9$
$1 \leq K \leq 10^9$
$1 \leq T_i \leq 10^9$
$C、K、T_i$ 均为整数

样例解释 1

比如，可以在时刻 $4.5$ 、 $6$ 、 $12$ 发车，并如下安排乘客乘车：

在时刻 $4.5$ 发车的巴士上，乘客为时刻 $2、3$ 到达的乘客。
在时刻 $6$ 发车的巴士上，乘客为时刻 $1、6$ 到达的乘客。
在时刻 $12$ 发车的巴士上，乘客为时刻 $12$ 到达的乘客。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页