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])