(ps:虽说这题是我在贪心类型里面做到的,但我完全没明白到底哪里是贪心)
战争已经进入到紧要时间。你是运输小队长,正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激,于是命令你的士兵们到前方的一座独木桥上欣赏风景,而你留在桥下欣赏士兵们。士兵们十分愤怒,因为这座独木桥十分狭窄,只能容纳 1 1 1 个人通过。假如有 2 2 2 个人相向而行在桥上相遇,那么他们 2 2 2 个人将无法绕过对方,只能有 1 1 1 个人回头下桥,让另一个人先通过。但是,可以有多个人同时呆在同一个位置。
题目描述突然,你收到从指挥部发来的信息,敌军的轰炸机正朝着你所在的独木桥飞来!为了安全,你的部队必须撤下独木桥。独木桥的长度为 L L L,士兵们只能呆在坐标为整数的地方。所有士兵的速度都为 1 1 1,但一个士兵某一时刻来到了坐标为 0 0 0 或 L + 1 L+1 L+1 的位置,他就离开了独木桥。
每个士兵都有一个初始面对的方向,他们会以匀速朝着这个方向行走,中途不会自己改变方向。但是,如果两个士兵面对面相遇,他们无法彼此通过对方,于是就分别转身,继续行走。转身不需要任何的时间。
由于先前的愤怒,你已不能控制你的士兵。甚至,你连每个士兵初始面对的方向都不知道。因此,你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外,总部也在安排阻拦敌人的进攻,因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。
输入格式第一行共一个整数 L L L,表示独木桥的长度。桥上的坐标为 1 , 2 , ⋯ , L 1, 2, \cdots, L 1,2,⋯,L。
第二行共一个整数 N N N,表示初始时留在桥上的士兵数目。
第三行共有 N N N 个整数,分别表示每个士兵的初始坐标。
输出格式共一行,输出 2 2 2 个整数,分别表示部队撤离独木桥的最小时间和大时间。 2 2 2 个整数由一个空格符分开。
样例 #1 样例输入 #14
2
1 3
样例输出 #12 4
提示对于 100 % 100\% 100% 的数据,满足初始时,没有两个士兵同在一个坐标, 1 ≤ L ≤ 5 × 1 0 3 1\le L\le5\times 10^3 1≤L≤5×103, 0 ≤ N ≤ 5 × 1 0 3 0\le N\le5\times10^3 0≤N≤5×103,且数据保证 N ≤ L N\le L N≤L。
解题思路:注意点1:士兵只能位于整数位置,可以有多个士兵位于同一位置,士兵相遇时会改变方向
也就是说,士兵在同一点时不一定改变自己的方向,只有方向不同时才会改变方向
接下来说明几种特殊情况,当士兵间距为1相向而行时,士兵会在1s后回到自己的原位,但是方向相反
当一名士兵遇到多名士兵时,多名士兵会同时反向,由此可见,其实在同一点的若干士兵可以看做一个士兵
注意点2:桥不应该被理解为线段,而应该被理解为点的集合,桥长代表点的数量,0 和 L+1点代表撤离点(区别于端点),相邻两点间距为1
接下来对解题思路进行说明
(1)最短时间:
最短时间 = max{士兵到撤离点距离的绝对值}
求最短时间时,只需要让士兵向着离自己最近的一端前进即可,很容易证明
(2)最长时间:
<1>如果只有一名士兵,最长时间是其到远端撤离点的距离
<2>有多名士兵,为了说明方便,我们把最左端士兵称为left,最右端士兵称为right,设 L 1 = r i g h t − l e f t L_1 = right - left L1=right−left那么有最长时间 = L 1 L_1 L1 + max{left, L + 1 - right}
接下来进行证明
我们只需要考虑 L 1 L_1 L1范围内的情况,至于为什么emmm,因为来到这个范围以外的士兵行为是单一的,后续处理就是简单的“+ max{left, L + 1 - right}",这点不予证明
如果有两名士兵,显然让他们对撞才是最长时间 L 1 L_1 L1
为了之后便于理解,这里说明一下,会发生对撞的两名士兵,从出发到再次回到起点,所需时间即为二者间距
如果有三名士兵,现在证明最长时间为 L 1 L_1 L1
两侧的士兵一定要向中间走,这是显然的
假设第三名士兵(之后称为middle)在中点右侧,现在讨论他的起始方向
middle若起始向左走,那么一定在中点左侧与left对撞,之后再与right对撞
设 D 1 = m i d d l e − l e f t D_1 = middle - left D1=middle−left, D 2 = r i g h t − m i d d l e D_2 = right - middle D2=right−middle
则
T
r
i
g
h
t
=
D
1
=
m
i
d
d
l
e
−
l
e
f
t
<
r
i
g
h
t
−
l
e
f
t
=
L
1
T_{right} = D_1 = middle - left< right - left = L_1
Tright=D1=middle−left
T
m
i
d
d
l
e
=
D
1
2
+
D
2
+
D
1
2
=
D
1
+
D
2
=
r
i
g
h
t
−
m
i
d
d
l
e
=
L
1
T_{middle} = \frac{D_1}{2} + D_2 + \frac{D_1}{2} = D_1 + D_2 = right - middle = L_1
Tmiddle=2D1+D2+2D1=D1+D2=right−middle=L1
T
l
e
f
t
=
D
1
2
+
D
2
+
D
1
2
=
D
1
+
D
2
=
r
i
g
h
t
−
m
i
d
d
l
e
=
L
1
T_{left} = \frac{D_1}{2} + D_2 + \frac{D_1}{2} = D_1 + D_2 = right - middle = L_1
Tleft=2D1+D2+2D1=D1+D2=right−middle=L1 middle若起始向右走,则在middle与right对撞后,middle会再与left对撞 则
T
r
i
g
h
t
=
D
2
2
+
D
1
+
D
2
2
=
L
1
T_{right} = \frac{D_2}{2} + D_1 + \frac{D_2}{2} = L_1
Tright=2D2+D1+2D2=L1
T
m
i
d
d
l
e
=
D
2
2
+
D
1
+
D
2
2
=
L
1
T_{middle} = \frac{D_2}{2} + D_1 + \frac{D_2}{2} = L_1
Tmiddle=2D2+D1+2D2=L1
T
r
i
g
h
t
=
D
2
<
L
1
T_{right} = D_2< L_1
Tright=D2 综上所述,最长时间为
L
1
L_1
L1 实现代码如下: 你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧#include
网页题目:独木桥(C++,贪心)-创新互联
新闻来源:http://cdkjz.cn/article/cddspi.html