题目:
一栋 10 层的大楼 (楼层编号 1-10), 设有一台无限载重的电梯, 初始时电梯停在 1 层电梯移动 1 层的耗时为 1, 在某一层停靠的耗时为 1(时间初始为 0) 为了使得乘客等待的时间 (电梯在目的层的停靠时刻 - 乘客发出请求时刻) 总和最小, 请你编写一个程序来进行电梯调度
输入有 5 个请求, 每个请求一行, 格式为
请求时刻起始楼层数去往方向
, 其中方向为 0 代表向上去往 10 层, 为 1 代表向下去往 1 层
输出每次对应的决策, 每一行的输出格式为
xx 时, 停靠在 x 楼
其中, xx 时刻指的是在某层楼停靠的时刻, 且不算入在该层的停靠时间如:
当 0 时刻时, 电梯此时在 1 层, 输入有 0 1 0, 那么电梯从 1 层接客 (1s) 前往 10 层(9s), 应输出
10 时, 停靠在 10 楼
(1+9=10)此时, 该乘客等待时间为(10-0=)10
当 0 时刻, 电梯此时在 1 层, 输入有 0 2 0, 那么电梯从 1 层前往 2 层(1s), 接上乘客(1s), 前往 10 层(8s), 应输出
10 时, 停靠在 10 楼
(1+1+8=10)此时, 该乘客等待时间为(10-0=)10s
最后输出完成 5 个请求 (所有乘客都到达目的地) 后, 各乘客的等待时间总和
请自己设计 5 组测试用例, 且具有一定代表性, 用以验证程序是否是最小耗时
编程语言选择 C 或 C++ 都可以, 但需要符合编码规范, 且必须要有注释要求在 github 上建立一个仓库, 将本次作业代码提交到该仓库, 并在博客开头给出仓库地址注意: commit 信息要遵守一定的 git 规范(可参看: git commit 规范指南),git 必须使用命令行操作, 不要使用 github 图形界面(可参看: 廖雪峰 Git 教程)
看完问题开始写, 直接冲着最优, 码了六七十行, 果断放弃, 我还年轻, 我不想掉头发??
咨询了学姐还是决定从最简单的开始开始吧
提交的跟我们日常单部电梯运行的算法比较类似(不能预知请求)
就是判断接下来的时间路径上是否有人可以搭顺风车, 最大的通病是, 电梯在 2~9 层并不会掉头
因为对象的概念和用法并不是很了解, 所以用了结构体来实现乘客的数据管理
最终提交代码:
version | 行数 | debug 数 | 用时 |
---|---|---|---|
initial | 85(117) | 16 | 18h |
继续改进中
Pintia
来源: http://www.bubuko.com/infodetail-2494111.html