题目描述
一名男子在12:00抵达了某巴士站,并且在12:00-12:59期间他将在那里逗留。
巴士站有很多巴士路线,巴士抵达的时间均已给出。
该男子观察巴士的抵达时间,有所发现:
1、在12:00 ~12:59 期间,同一线路上的巴士以相同的时间间隔到站。
2、每条巴士线路至少有两辆车到达本站。
3、不同线路的巴士可以同时到达本站。
4、不同巴士线路的车首次到达本站的时间和到站的时间间隔都有可能相同。
5、测试用例中的总线路不会超过17条。
请你编写一个程序,求出在所有巴士到达本站的时刻满足输入数据的要求的情况下,巴士线路的总数量最小是多少。
样例
输入样例:
17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53
输出样例:
3
算法1
(迭代加深 + 剪枝)
预处理:
预处理出所有可能的线路。先枚举起点i
, 再枚举公差j
, 则i
和 j
需要满足两个条件:
- 由于
i
是起点, 因此0 ~ i - 1
中不能包含任何起点,所以公差至少为i + 1
; - 由于
0 ~ 59
之间至少包含两个点, 因此i + j < 60
剪枝:
1.因为答案结果为组合数,需要考虑顺序问题,因此从起点小的开始枚举。
2.所有等差数列按长度排序, 长度较长的开始递归搜索,因为递归深度小。
3.由于有剪枝2, 当前选择的线路是覆盖点数最多的,如果 (当前覆盖的点数 * 剩余可选择的路线数量 + 当前已经覆盖的点数 < 总点数), 则方案不合法,回溯。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 2010, M = 60;
int n;
vector<pair<int, PII>> routes;
int bus[M];
bool is_route(int a, int d){
for (int i = a; i < 60; i += d)
if (!bus[i])
return false;
return true;
}
bool dfs(int depth, int u, int sum, int start){
if (u == depth) return sum == n;
if (routes[start].first * (depth - u) + sum < n) return false;
for (int i = start; i < routes.size(); i ++ ){//每层按照等差数列长度从大到小遍历。
auto r = routes[i];
int a = r.second.first, d = r.second.second;
if (!is_route(a, d)) continue;
for (int j = a; j < 60; j += d) bus[j] --;
if (dfs(depth, u + 1, sum + r.first, i)) return true;//纵向方向都从i开始寻找。因为i是等差数列长度最长的线路。
for (int j = a; j < 60; j += d) bus[j] ++;
}
return false;
}
int main(){
scanf("%d", &n);
for (int i = 0; i < n; i ++ ){
int t;
scanf("%d", &t);
bus[t] ++;
}
for (int i = 0; i < 60; i ++ )
for (int j = i + 1; i + j < 60; j ++ )
if (is_route(i, j))
routes.push_back({(59 - i) / j + 1, {i, j}});
sort(routes.begin(), routes.end(), greater<pair<int, PII>>()); //剪枝2
int depth = 0;
while (!dfs(depth, 0, 0, 0)) depth ++;//剪枝1,从起点开始枚举
printf("%d\n", depth);
return 0;
}