/ ep / 题库 /

独木桥

独木桥

题目描述

有一条长度为L的独木桥,桥上有N个士兵,士兵会以每秒1个单位的速度沿着他们面向的方向前进,若两个士兵相遇,则他们会调转再继续走
若一个士兵走到了0或者L+1的位置就视为他已经离开了独木桥
现在,我们知道每个士兵一开始的位置,但不知道他们一开始面朝的方向,在这样的情况下,请求出所有士兵都离开独木桥需要花费的最短和最长时间

输入

第一行,两个整数:L和N
第二行,N个整数,分别表示N个士兵的初始位置

输出

第一行一个整数,表示所有士兵都离开独木桥花费的最短时间(单位:秒)
第二行一个整数,表示所有士兵都离开独木桥花费的最长时间

输入样例

4 2
1 3

输出样例

2
4

数据范围与限制

对于30分的数据,有\(L\leq100\)
对于60分的数据,有\(N\leq50,L\leq3000\)
对于100%的数据,有\(N\leq L\leq2000000\),所有士兵的初始位置互不相同
时间限制1s,空间限制256m

信息

ID
1007
难度
4
分类
贪心 | 模拟 点击显示
标签
(无)
递交数
2
已通过
1
通过率
50%
上传者

相关

在下列训练计划中:

新生入门训练计划