因为前几天开始随意做了一个JD的题目，于是就打算逐步把JD在赛码网上的5-3星难度的题目做完，比较有价值的题目会有比较详细的分析过程，其余的就阐述重点或简单带过即可。因为5星难度题目只有两个，就倒着来做好了。
这次的解析包含了3个4星难度题目，并且从其中一个题目来介绍双端队列的概念和使用。
保卫方案
<题目来源: 京东2017秋招 原题链接-可在线提交(赛码网)>
问题描述
先准确理解题意：在一个环上有若个点，每个点都和它相邻的两个点连通，选定其中任何两个点a和b，如果a从顺时针或者逆时针方向到b所经过的点没有比a和b中较小的点更高时(注意如果3个点的高度相等时候，是可以相互观察的)，a和b可以相互观察。最终我们需要知道有多个这样的(a, b)对。
实际上，最简单粗暴的办法就是3一个三重循环进行扫描，首先2重循序去枚举一个观察对(a, b)，再用一重循环检查(a, b)中有没更高的山就可以了。
好消息是这个题目数据很弱，这个O(n^3)的算法完全可以通过测试，赛码网上的大多数人也是用的这个方法。
坏消息是这并不是一个很好方法，如果按题目给定的数据规模是无法通过的。
接下来我们来观察这样一个O(n^3)的算法的执行过程，并从中找到一些可以优化的地方。首先，在不考虑环并且我们选定顺时针方向的情况下，我们计算(a, b)是否可以相互观察，我们会扫描mount[a + 1], mount[a + 2], ... mount[b - 1]，在扫描的过程中如果发现第一个mount[i] > mount[a]，那么此后任何点都不能被a观察到。
a.如果我们在扫描的过程中，发现mount[a + 1] > mount[a]，那么a就不能观察到后续的任何点，也就没有必要对后面的点再进行扫描后了。接下来，如果mount[a + 2] > mount[a + 1]，这个过程是同样的，mount[a + 1]同样无法观察到之后的任何一个点，同样不需要扫描。如果整个mount[i]是一个单调递增的序列，显然除了相邻的两个点可以观察，其余任何两个点是无法观察的(这里不暂考虑环的情况)。
b.如果mount[a + 1] < mount[a]，那么mount[a]就有可能观察到a + 1后面的点，因此我们需要再看接下来的情况，这个时候假设mount[a + 2] > mount[a + 1]，显然是mount[a]可以观察到mount[a + 2]，而mount[a + 1]不能再观察到后续的任何点(规则a说明)，假设mount[a + 2] < mount[a + 1]，那么mount[a + 2]也可能观察到后面的点，需要继续看接下来情况。
综合上面2点规则，我们需要维护一个不递增(注意，是不递增，而不是递减，这就说明了有相等的情况)这样一个单调性的线性结构，当向这个线结构中加入一个mount到尾部时，我们就从尾部一个mount一个mount的和当前加入的这个进行比较，如尾部的这个mount < 当前加入的，就需要将这个尾部mount移除，继续这个比较，直到线性结构中的某个mount >= 当前加入的，或者整个线性结构已经移除了所有的mount。还应当注意到，新加入mount和出队的所有mount都是可以相互观察，此外，相邻的两个mount可以相互观察。
现在我们需要一个支撑我们实现上述操作的数据结构--双端队列(deque)，双端队列是一个可以在队列的任何一端都可以进行入队和出队操作的一个数据结构。对这个在题目而言，我们在队首进行出队操作(一会在解决环的问题的时候会用到)，在对尾进行入队和出队操作。
接下来，需要解决的就是环的问题。解决环的方式一般可以采用将原来的环切段，并且从切断位置再复制一份这个断掉的环(也就是一根链了)，还有就是取模的形式。都可以。对于这个问题，我们只需要从当前位置考虑到后面n个位置即可。例如，现在n=5 共有5个mount,在处理mount[3]的时候，我们需要向后考察mount[4],mount[5]，然后是mount[1]，最后是mount[2]。也就是，双端队列中只需要保留最多n个的mount，第n+1个加入的时候，需要将第1个从队首出队。再来观察个例子，现在n=5,且这个5个mount的高度都是不单调不增长的，当n=5进入双端队列时，队列中有5个元素，当第6个mount入队时(实际上是第一个)，显然就产生了重复，1不需要再观察到自己，更不需要绕过自己一圈再观察后面的mount，所以，此时应该将1从队首中出队。
至于题目任何两个mount可以从两个通路观察(顺时针或者逆时针)，其实已经不需要处理，因为我们都从任何1个点向一个方向观察了n个长度，从mount[a]如果可以观察mount[b]，也就是从mount[b]可以观察mount[a]，也就是我们在处理a时考察了a->b是否可以观察，在处理b时，考察了b->a是否可以观察。由于可能会有重复的情况，因此我们需要设置一个set类型(而不是obv[][]这样一个二维数组来标记，要知道题目的数据规模是n=10^6)来保存从任何一点能观察的其他的点,这样的存储空间也比较理想。
至此，问题还没有解决。还有一个相等的问题需要处理，也就是同样高的mount，因为题目是要求两个mount之前没有更高的mount就可以观察。因为3个或者更多相等的mount中，只要没有更高的，也是可以相互观察的。这部分我们在双端队列中处理时，如果遇到相等，要继续向前找到不相等的。但是不要将这些mount出队。
至于算法复杂度，前面我简单到提到过，尽管下面的代码也使用了3层的循环，但要注意实际的执行次数，任何一个元素在双端队列中最多被入队一次，出队一次(不考虑重复的情况)。
import sys
const_val = 0
const_num = 1
result = 0
def add_pair(a, b, pair):
global result
if a > b:
a, b = b, a
if b not in pair[a]:
pair[a].add(b)
# print a + 1, b + 1
result += 1
def main():
global result
while True:
result = 0
h = []
deque = []
line = map(int, sys.stdin.readline().strip().split())
if len(line) < 1:
return
n = line[0]
line = map(int, sys.stdin.readline().strip().split())
for elem in line:
h.append(elem)
pair = [set() for i in range(n)]
for i in range(2 * n):
seq = i if i < n else i - n
if len(deque) and deque[0][const_num] == seq:
deque.pop(0)
while len(deque) > 0:
t = deque[-1]
add_pair(t[const_num], seq, pair)
if deque[-1][const_val] < h[seq]:
deque.pop(-1)
else:
for q in deque[::-1]:
add_pair(q[const_num], seq, pair)
if q[const_val] != h[seq]:
break
break
deque.append((h[seq], seq))
print result
if __name__ == '__main__':
main()备考
<题目来源: 京东2016实习生 原题链接-可在线提交(赛码网)>
问题描述
虽然都是4星题目，剩下两个题目相对就很简单了。并且剩下两个头目比较类似，我们作为一类问题处理吧。
这个题目因为每天最有个最大和最小的限制。我们先来考虑可行性，也就是只需要考察两个极端情况是否满足总的学习时间。
∑MinTimeDay[i] <= sumTime <= ∑MaxTimeDay[i] i∈[1..n]
满足后，根据题目要求尽可能在前面的天数多学习，那么我们从头开始处理，首先保证满足每天的最低时间，剩余的sumTime - ∑MinTimeDay[i]尽可能的从一开始就多分配，但不要超过MaxTimeDay[i]，用完后，其余的就按MinTimeDay[i]时间学习即可。
import sys
def main():
day = []
while True:
line = map(int, sys.stdin.readline().strip().split())
if len(line) < 2:
return
d, sum_time = line[0], line[1]
t_min = 0
t_max = 0
for i in range(d):
line = map(int, sys.stdin.readline().strip().split())
day.append((line[0], line[1]))
t_min += line[0]
t_max += line[1]
if t_min <= sum_time <= t_max:
sum_time -= t_min
print 'Yes'
for d in day:
if d[1] - d[0] <= sum_time:
print d[1],
sum_time -= d[1] - d[0]
elif 0 < sum_time < d[1] - d[0]:
print d[0] + sum_time,
sum_time = 0
else:
print d[0],
print
else:
print 'No'
day[:] = []
if __name__ == '__main__':
main()爬山
<题目来源: 京东2017秋招 原题链接-可在线提交(赛码网)>
问题描述
解决这个题目我们需要按d作为key进行一个排序，按时间整理爬山的高度后，考察两个横向的距离，也就是间隔的天数。因此题目规定每天只能上下最多一个单位高度，因为间隔的天数决定了我们在纵向可以移动的高度。
首先检查第i个记录和i+1个记录的合理性。
abs(reci + 1 - reci) <= reci + 1 - reci
计算最大可达到的高度
h = (reci + 1 - reci + reci + 1 + reci) / 2
最后注意两个端点的处理即可。
import sys
const_d = 0
const_h = 1
def main():
while True:
rec = []
line = map(int, sys.stdin.readline().strip().split())
if len(line) < 2:
return
n, m = line[0], line[1]
for i in range(m):
line = map(int, sys.stdin.readline().strip().split())
rec.append((line[0], line[1]))
rec = sorted(rec)
flag = True
result = 0
for i in range(m - 1):
if abs(rec[i + 1][const_h] - rec[i][const_h]) > rec[i + 1][const_d] - rec[i][const_d]:
flag = False
print 'IMPOSSIBLE'
break
else:
h = (rec[i + 1][const_d] - rec[i][const_d] + rec[i + 1][const_h] + rec[i][const_h]) / 2
# print '---->', h
hy_max = max(rec[i + 1][const_h], rec[i][const_h])
result = max(result, max(hy_max, h))
if flag:
hy_board_max = max(rec[0][const_h] + rec[0][const_d] - 1, rec[-1][const_h] + n - rec[-1][const_d])
result = max(hy_board_max, result)
print result
if __name__ == '__main__':
main()