第四题
我觉着正确的解法是 应该是 先用一个结构体保留每个基站的位置和高度 然后按高度排序 每次以刚好每个基站的高度去淹没(根据左右1 0淹没情况,在前一个高度洪水淹没情况的值上进行推导) 用一个数组记录 最后 只要二分找到刚好大于等于基站高度的洪水的值 就是该答案 (还要注意 高度相同的情况 直接按上面的情况算 然后取后面的值覆盖相同高度基站的值就可以了)
区间线段树试过不行,因为数据太散,实际上还是到叶子节点,复杂度降不下来。