P3353 在你窗外闪耀的星星

· · 个人记录

题意分析

一维数轴整点上有许多的星星，如何开窗户才能看到最亮的星光

窗户的宽度是固定的，边缘是透光的，不过似乎也不准确。 应该说是窗户的边缘不一定恰好在格点上。

如同样例里宽度是 3，窗户开口是大概 1.5 - 4.5 的范围。也就对应这数轴上2、3、4 这 3 个位置的星光。宽度和位置一致。

也因此 w = 0 时，看不到星光。

一

朴素的想法是找到长度为 w 的区间，对每一个区间求和，保留最大值即答案。非常标准的模拟题意，正确性毋庸置疑。

对此，可以做一些简单的算术大概预估我们的程序会花多长的时间。我们将一次循环体运行的平均时间视为单位 1。

位置值域 1e5 ，区间数目 1e5-w+1 ，求一次区间和 w 单位时间。 最终结果即 (1e5-w+1)*w ， 那么最坏的情况下

取 w = 5e4 ，5e4*5e4 = 25e8 = 2.5e9 > 5e8

运行时间大概率会超过 1s。 这么说是以因为，一般 1s 内电脑运算次数大概 5e8 次左右，具体来说和电脑配置，常数大小有关，常数大致可以看作看作循环内代码行数。

以上的想法显然有重复的计算可以避免，毕竟相邻的两区间只有两个数不同，完全没必要全部单独累加一遍。

二

滑动窗口的思路由此诞生，加入窗口下一个位置的亮度，减去窗口头一个的亮度，一加一减，得到了下一个区间的亮度和。操作上和队列是很像的，不过没有必要具体的用到。预处理第一个区间的和，之后for循环就可以了

再次分析，第一个区间计算 w 次以求和，之后计算2次一个区间,这个2就是常数，忽略掉常数之后。w+(1e5-w+1) = 1e5 ，大概<1ms？ 时间复杂度降至 O(值域)

三

有一种变式的技巧也可以应用在这里。所以还是介绍一下，基础而应用广泛。

给出一个序列 a_n n 个整数 q 次询问，每次给出一个区间 [l,r]，询问区间和。

朴素的想法在每个区间几乎都是全域的时候 可能复杂度就到了 O(qn)。而且一直是大量冗余操作。

这时候引入前缀和 S_n = a_1 + a_2 + \dots + a_n

这个时候我们想要求一个左端点是1的区间 $[1,r]$ 和，如 $[1,3]

因为 S_3 = a_1 + a_2 + a_3。所以 S_r 即为答案，某种意义上的记忆化操作。

更普遍的区间 [l,r]之和 可以转化为 [1,r]之和 减去 [1,l-1]之和,也就是 S_r-S_{l-1} 即为区间和。 端点非常容易混淆

将原来每次询问消耗的 O(n) 降至 O(1),多一次减法，总的复杂度就是 O(n) 的了。

相信你也看出来了前缀和有时候被叫做离散积分

在P3353这道题里也可以应用前缀和 O(1) 的查询区间和，最后参考代码也是如此。

离散化

题目并没有依次给出每一位置的亮度，而是给位置和亮度，也即输入是离散化的。

星星太少，与其把空余的 0 补出来，不如把位置带上。

这道题可以离散化处理，也可以还原回去，append一个长长的数组来存每一个位置的星星的亮度。注意星星位置可能会重合

这个长长的数组对应一个list，完全可做的。坐标值域限于 1e5 这样一个范围内是完全可接受的。之前 3 种方法全都是这样做的。

不过值域进一步扩大的话，如果是 1e9 的话……这样大小的list 对内存空间的占用不容小觑，至少 4G 运行内存会被你的程序吞掉。内存不足是会报错，程序没法正常运行。

仅仅 1e5 颗星星 当然有办法可以减少空间的占用，这也就是 离散化

值域很广，但是数量不多，都可以离散化，某种意义上的“缩点”，把之间的空余略去，存下标和亮度

这里正好输入格式相符。

由于是乱序的，所以要排序。

星星位置可能会重合 ，所以要合并一些星的亮度，方便处理，回避错误。顺带列表可修改，元组不可修改。

前缀和初始化是一样的，不过在询问的时候区间长度就会变了，缩点时大概率是不一样多的。

代码解析

读入

第一行的星星数量 n 和窗户宽度 w

接下来 n 行的星星按照 "位置 亮度" 给出

一行用空格隔开的两个整数，如何读入？

需要先用split函数从空格分成两个

line = input().split()
n = int(line[0])
width = int(line[1])

那么读入就没问题了。

特判

exit(0) 以正常的返回值结束程序，不想写 if-else 罢了。

最后那里，w = 0 时，左端点l 会跑到 r 右边，可能会访问越界 RuntimeErorr

即便没有越界，答案不应该得到更新，因为答案肯定是 0

去重

我用的字典，因为我是先去重后排序。

你可以先排序，再去重，就用不到字典。

只有列表是可修改的序列，字符串/元组不能修改

排序

二维列表排序，sort需要关键字参数key传一个函数决定标准 lambda 匿名函数 a.sort(key = lambda x: x[1])

和以下写法等效

def Compare (x):
    return x[1]
a.sort(key = Compare)

预处理前缀和 S_n

所以s列表作为原始列表没覆盖是有好处的。

前缀和有另一种写法

[l,r]$ 之和 = $S_r-S_{l} + a_l

这样就不需要手动前置 0 项。从 0 开始，全部高效利用。

尺取法

初始化前缀和列表之后，才是算法的主体。

以下结合代码来读。 假设窗框左右端点分别为 l,r

>写一个队列，右端点先走(r += 1)，走完区间长度增加，看看左端点有没有落后(超过窗框)，落后就跟上来(l += 1)。 > >r 走一次更新一次答案。l,r 都只扫过一遍离散化后的数组，时间复杂度 O(n) 最后输出答案 总时间复杂度瓶颈在排序 $O(n\log n)

附

当然还有很多的 python 语法实现、 IPO模型