今天上了些强度。 思路 首先，注意到题目输入规模可能较大，n 可能达到 10^9，也就是说从 1 到 n 单趟扫描都是难以接受的，显然我们应该按 restrictions 去处理。 题目给的限制： id=1 的建筑高度必须是 0（相当于首个限制点） 相邻两栋高度差不能超过 1 受 restrictions 中限制点限制的 id 处建筑高度不能超过指定限制 如果没有限制点，就 1, 2 两点说，我们让建筑高度不断递增其实就行了，这个时候 id 差就是两个建筑间的高度差。因为相邻高度差不能超过 1，显然两个建筑间的最大高度差（或最大高度变化量）就是 id 差。 因为规模可能很大，我们只能按 restrictions 中的限制点进行处理： 每个限制点处建筑的最大高度受 \mathrm{maxHeight}_i 以及左右相邻建筑的高度约束 要知道左右相邻建筑的高度约束情况，我们需要从左往右，从右往左扫描处理 restrictions 先对 restrictions 按 id 排序，按两个方向扫描： 从左往右时，设当前限制点编号是 \mathrm{id}_i，限制高度...