9月9日360 算法笔试
第一题
给定一个一维数组表示不同地方的高度，然后在一个地方倒水。倒水会使得相邻的低于此地高度的地方积水。问最多多少个地方积水。
第二题
有一个长度为n的棋子队列，初始情况为全正面。对其做q次操作，每次操作会将[a,b]区域内的棋子翻转。问每次操作过后的正面棋子个数。
解法
一开始想维持一个线段队列，然后记录每个队列的正反情况。但是发现在插入新的线段时，要考虑的情况太多了：新线段包含已有线段，新线段和其中一个相交等等。
所以新的想法就是每次就将线段的两端记录下来，每次遇到一端就翻转。统计正反的棋子个数。
n, q = [int(x) for x in input().split()]
lines = [0, n]
for _ in range(q):
a, b = [int(x) for x in input().split()]
lines.append(a-1)
lines.append(b)
lines = sorted(lines)
c = 1
dic = {0:0, 1:0}
prev = 0
for i in lines[1:]:
cur = int(i)
dic[c] += cur - prev
c = 1 - c
prev = cur
print(dic[1]) #360笔试#
类似资料：