最小化蒙德城的旅行者队伍（巴士）

本文主要是介绍最小化蒙德城的旅行者队伍（巴士），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

在阳光明媚的一天，凯亚在蒙德城的风车塔下等待着前往狼的领域的旅行者。他于12:00抵达，并计划在此地逗留一整小时，直至12:59。

蒙德城有许多旅行者的车队，每个车队都有自己的出发时间表。

凯亚观察了这些车队的出发时间，并记录了以下发现：

1. 在12:00至12:59期间，同一车队的旅行者会以相同的时间间隔到达风车塔。
2. 每个车队至少有两名旅行者在这一时间段到达。
3. 不同车队的旅行者可以同时到达风车塔。
4. 不同车队的旅行者首次到达风车塔的时间和到达的时间间隔都有可能相同。
5. 测试用例中的车队总数不会超过17个。

请你帮助凯亚编写一个程序，求出在所有旅行者到达风车塔的时刻满足输入数据的要求的情况下，车队的总数量最小是多少。

输入

输入数据第一行包含整数 n，表示在这一小时内抵达到风车塔的旅行者总数量。

第二行包含 n 个整数，表示按升序排序得到的 n 个旅行者的到达时间。

1≤n≤300

输出

输出一个整数，表示最小车队数。

输入样例 1 

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

输出样例：

3

思路：

最开始我想得是枚举所有的起点然后开始深搜，但是发现这样时间复杂度太高了，所以参考了y总的代码。

先预处理出所有可能的路线：先枚举起点 i，再枚举公差 j。

由于i是起点，因此0 ~ i - 1中不能包含任何该序列的点，所以公差j至少是i + 1；
由于0 ~ 59之间至少要包含两个点，因此i + j一定小于60；

剩下的问题变成：最少从合法线路中选出多少条，才可以覆盖所有给定的公交车。

剪枝：

①由于是枚举组合数，并不是排列数，为了避免重复在DFS时传入当前枚举的起点。
②将所有等差数列按长度排序，优先枚举长度较长的等差数列。这样在搜索树中前几层的分支少，可以更快地发现矛盾然后回溯。
③由于剪枝2的存在，当前路线覆盖的点数是最多的，如果当前路线能覆盖的点数 * 剩余可选的路径条数 + 当前已经覆盖的点数 < 总点数，说明当前方案一定非法，直接回溯即可。

代码实现

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int M=60;
int n;
int time[M];//用于记录时间t到达的旅行者的个数
//存储该路径旅行者的个数、起点、差值
vector<pair<int,PII>> routes;bool is_route(int a,int d)
{//判断是否为可行解for(int i=a;i<60;i+=d)if(!time[i])return false;return true;
}
bool dfs(int depth,int u,int sum,int start)
{//sum记录当前已经安排的旅行者人数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;//由于枚举过程中time数组会改变所以要再次判断for(int j=a;j<60;j+=d)time[j]--;if(dfs(depth,u+1,sum+r.first,i))return true;for(int j=a;j<60;j+=d)time[j]++;//恢复现场}return false;
}
int main()
{scanf("%d",&n);for(int i=0;i<n;i++){int t;scanf("%d",&t);time[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>>());int depth=0;while(!dfs(depth,0,0,0))depth++;printf("%d\n",depth);return 0;
}

这篇关于最小化蒙德城的旅行者队伍（巴士）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---