当前位置: 首页 > article >正文

http://noi.openjudge.cn/——4.7算法之搜索——【169:The Buses】

题目

169:The Buses
总时间限制: 5000ms 内存限制: 65536kB
描述
A man arrives at a bus stop at 12:00. He remains there during 12:00-12:59. The bus stop is used by a number of bus routes. The man notes the times of arriving buses. The times when buses arrive are given.
Buses on the same route arrive at regular intervals from 12:00 to 12:59 throughout the entire hour.
Times are given in whole minutes from 0 to 59.
Each bus route stops at least 2 times.
The number of bus routes in the test examples will be <=17.
Buses from different routes may arrive at the same time.
Several bus routes can have the same time of first arrival and/or time interval. If two bus routes have the same starting time and interval, they are distinct and are both to be presented.

Find the schedule with the fewest number of bus routes that must stop at the bus stop to satisfy the input data. For each bus route, output the starting time and the interval.
输入
Your program is to read from standard input. The input contains a number n (n <= 300) telling how many arriving buses have been noted, followed by the arrival times in ascending order.
输出
Your program is to write to standard output. The output contains one integer, which is the fewest number of bus routes.
样例输入
17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53
样例输出
3
来源
IOI 1994

翻译

描述
一名男子于12:00到达公交车站。他在12:00-12:59期间留在那里。公共汽车站被许多公共汽车路线使用。
那人记下了到达的公共汽车的时间。公共汽车到达的时间已经给出。
同一路线的公共汽车在整个小时内从12:00到12:59定期到达。
时间以0到59的整分钟为单位。
每条公交线路至少停靠2次。
测试示例中的公交线路数量将<=17。
不同路线的巴士可能会同时到达。
多条公交线路可以具有相同的首次到达时间和/或时间间隔。如果两条公交线路的出发时间和间隔相同,
则它们是不同的,并且都要呈现。
找到必须在公交车站停靠的公交线路数量最少的时刻表,以满足输入数据。对于每条公交线路,输出起始时间和间隔。

输入
您的程序将从标准输入读取。
输入包含一个数字n(n=300),表示记录了多少辆到达的公交车,
后面是按升序排列的到达时间。

输出
您的程序将写入标准输出。输出包含一个整数,这是最少的公交线路数量。

理解

1.每个停靠时间都能划归一条线路
2.每个没归入线路的停靠时间都可以作为一个公交小路
3.公交线路的两个相邻停靠时间间隔一样
4.停靠的次数不能少于2,也就是只有一次差。任何两个停靠之间都可以作为一线路
5.如果所有的时间线都找到线路就算搞定

代码(参考网上找到的代码)

#include <bits/stdc++.h>
using namespace std;
struct Stop_time{//停靠一次
int time,//时间点
id,//哪个公交线路
m;//该时间点停靠了几个线路
}stop_time[60];
struct Bus_line{//公交线路
int first,//首次停靠时间
time,//间隔时间
m;//该线路停靠总次数
Bus_line(){};
Bus_line(int firstx,int timex,int mx){first=firstx,time=timex,m=mx;};
bool operator<(Bus_line b){
return m>b.m;
}
}bus[900];
int n,//共停靠次数
x_time,//输入停靠时间
bus_m,//可能线路总数
ans=17;//题目给定的最多公交线路,找最少的
void view1(string s){
cout<<s<<endl;
cout<<“首停时间”<<“\t间隔时间”<<“\t停靠车数”<<endl;
for(int i=0;i<bus_m;i++)cout<<bus[i].first<<“\t\t”<<bus[i].time<<“\t\t”<<bus[i].m<<endl;
}
void view2(int x){
cout<<“线路”<<x<<“\t首次停靠时间:”<<bus[x].first<<“\t间隔时间:”<<bus[x].time<<“\t停靠次数”<<bus[x].m<<endl;
cout<<“时间\t”;for(int i=0;i<60;i++)if(stop_time[i].time)cout<<i<<“\t”;cout<<endl;
//cout<<“有停靠\t”;for(int i=0;i<60;i++)if(stop_time[i].time)cout<<stop_time[i].time<<“\t”;cout<<endl;
cout<<“停几车\t”;for(int i=0;i<60;i++)if(stop_time[i].time)cout<<stop_time[i].m<<“\t”;cout<<endl;
cout<<“线路\t”;for(int i=0;i<60;i++)if(stop_time[i].time)cout<<stop_time[i].id<<“\t”;cout<<endl;
}
int check(int first,int time){//判断该线路是否成立
if(first>=time)return 0;//初始停靠时间超过往返时间,意味着不是首次停靠,不是始发
int total=0;//总共停靠次数
for(int i=first;i<60;i+=time){//遍历所有时间
total++;
if(stop_time[i].m= =0)return 0;//如果某个时间点没有停靠,该线路不成立
}
return total;
}
//go(线路序号,哪个线路,已定线路数,确定了几个停靠时间)
void go(int id,int x,int num,int total){
if(total==n){ans=min(ans,num);return;}
for(int i=x;i<bus_m;i++){//从大到小,先用多的线路
if(num+(n-total)/bus[i].m>=ans)return;//已定线路数+剩余停靠次数/该线路所用停靠次数>最少线路数
if(check(bus[i].first,bus[i].time)){//判定该线路所需停靠时间被前面线路用了没
for(int j=bus[i].first;j<60;j+=bus[i].time){
stop_time[j].m–;//该线路占用停靠时间
stop_time[j].id=id;//该线路占用停靠时间
}
//view2(i);
go(id+1,i,num+1,total+bus[i].m);//递归,多个线路,多该线路的停靠次数。
for(int j=bus[i].first;j<60;j+=bus[i].time){
stop_time[j].m++;//该线路占用停靠时间
stop_time[j].id=0;//该线路占用停靠时间
}
}
}
}
int main(){
freopen(“data.cpp”,“r”,stdin);
cin>>n;
for(int i=0;i<n;i++){
cin>>x_time;
stop_time[x_time].m++;
stop_time[x_time].time=x_time;
}
for(int i=0;i<30;i++)//线路始时间
for(int time=i+1;time<60-i;time++){//该线路往返周期
int total=check(i,time);
if(total)bus[bus_m++]=Bus_line{i,time,total};
}
//view1(“排序前”);
sort(bus,bus+bus_m);//为找最少线路,从停靠次数最多线路开始
//view1(“排序后”);
//go(线路序号,哪个线路,共几个线路,占用了几个停靠时间)
go(1,0,0,0);
cout<<ans;
return 0;
}

所有可能线路

在这里插入图片描述

结果

在这里插入图片描述

小结

该题递归本身不难,难的是不超时。
特别关键的思路,是先找到所有可能的线路,停靠时间间隔一样的线路,间隔不能小于第一次停靠的时间,起码得停靠两次。
并且以此为可能线路的判断。
以停靠次数为序降序排序。
递归遍历所有线路,每次从线路始停时间,间隔时间,消除所有停靠时间。
对,线路的预选,线路的判断是难点。


http://www.kler.cn/a/510845.html

相关文章:

  • C语言之整数转换英文表示
  • SVG(Scalable Vector Graphics)全面解析
  • 通信协议之数据帧常用校验方法(奇偶校验、CRC校验)
  • 运动相机拍视频过程中摔了,导致录视频打不开怎么办
  • 【大数据2025】Yarn 总结
  • 3. 后端验证前端Token
  • 《王者荣耀》皮肤爬虫源码
  • 【漫话机器学习系列】050.epoch(迭代轮数)
  • 数字艺术类专业人才供需数据获取和分析研究
  • 解决Oracle SQL语句性能问题(10.5)——常用Hint及语法(6)(并行相关Hint)
  • 接口测试Day10-测试数据封装(参数化-数据驱动)
  • 【氮化镓】香港科技大学陈Kevin-单片集成GaN比较器
  • TensorFlow深度学习实战(5)——神经网络性能优化技术详解
  • Linux磁盘空间不足,12个详细的排查方法
  • 【LeetCode: 215. 数组中的第K个最大元素 + 快速选择排序】
  • NavVis手持激光扫描帮助舍弗勒快速打造“数字孪生”工厂-沪敖3D
  • SpringMVC (1)
  • Ability Kit-程序框架服务(类似Android Activity)
  • 【机器学习】制造业转型:机器学习如何推动工业 4.0 的深度发展
  • 【2024年华为OD机试】(C卷,100分)- 悄悄话 (Java JS PythonC/C++)
  • Mac的`~键打出来±§`?解析ANSI、ISO、JIS键盘标准的区别与布局
  • C++ random_shuffle函数:从兴起到被替代
  • C++连接使用 MySQL Connector/C++ 库报错bad allocation
  • 怎么查看 centos5 是否安装 mysql
  • HTML应用指南:利用GET请求获取微博用户特定标签的文章内容
  • 2025最新版PyCharm安装使用指南