巴士路线问题

题目描述

一名男子在 12:00 抵达了某巴士站，并且在 12:00∼12:59 期间他将在那里逗留。

巴士站有很多巴士路线，巴士抵达的时间均已给出。

该男子观察巴士的抵达时间，有所发现：

观察规则

1. 在 12:00∼12:59 期间，同一线路上的巴士以相同的时间间隔到站。
2. 每条巴士线路至少有两辆车到达本站。
3. 不同线路的巴士可以同时到达本站。
4. 不同巴士线路的车首次到达本站的时间和到站的时间间隔都有可能相同。
5. 测试用例中的总线路不会超过 17 条。

问题

请你编写一个程序，求出在所有巴士到达本站的时刻满足输入数据的要求的情况下，巴士线路的总数量最小是多少。

输入格式

输入数据第一行包含整数 n，表示在这一小时内抵达到该站的巴士总数量。

第二行包含 n 个整数，表示按升序排序得到的 n 个巴士的到站时间。

输出格式

输出一个整数，表示最小巴士线路数。

数据范围

$1 \le n \le 300$

输入样例

17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53

输出样例

3

样例解释

巴士到站时间（分钟数，从12:00开始）： 0, 3, 5, 13, 13, 15, 21, 26, 27, 29, 37, 39, 39, 45, 51, 52, 53

最少需要 3 条巴士线路。

一种可能的线路分配方案：

线路1：时间间隔为 13 分钟

• 首次到站时间：0分钟（12:00）
• 后续到站时间：13分钟（12:13）、26分钟（12:26）、39分钟（12:39）、52分钟（12:52）
• 覆盖的时间点：0, 13, 26, 39, 52

线路2：时间间隔为 3 分钟

• 首次到站时间：3分钟（12:03）
• 后续到站时间：6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57
• 但根据给定数据，实际到站时间点有：3, 15, 21, 27, 39, 45, 51

线路3：时间间隔为 5 分钟

• 首次到站时间：5分钟（12:05）
• 后续到站时间：10, 15, 20, 25, 30, 35, 40, 45, 50, 55
• 但根据给定数据，实际到站时间点有：5, 15, 29, 37, 39, 53

注意：

• 有些时间点（如15, 39, 45）可能被多条线路共享
• 有些时间点（如13）只出现在一条线路中
• 所有17个时间点都被这三条线路覆盖

关键约束

1. 时间范围：所有时间在 0-59 分钟内（12:00到12:59）
2. 相同线路：同一线路的巴士到站时间构成等差数列，公差（间隔）相同
3. 最少车辆：每条线路至少有两辆车到站（即至少有两个时间点）
4. 线路数量限制：总线路数不超过17条（这是上限，我们需要找最小值）
5. 时间点可能重复：输入中可能包含相同的时间（如样例中的13和39都出现了两次）

问题转化

给定一个时间点集合，需要将这些时间点划分为最少数量的等差数列（每条线路对应一个等差数列），使得：

• 每个时间点至少属于一个等差数列
• 每个等差数列至少包含两个时间点
• 等差数列的公差（时间间隔）是正整数

时空限制

• 时间限制：1秒
• 空间限制：64MB