%%%zak
这里 DS 给我写了一个很形象的比喻,可以很好的理解这个原理:
"懒人监控系统" 比喻
想象你是个保安,要监控多个房间的温度总和不能超过100度:
传统方法(笨保安):
每隔1分钟就跑去所有房间读温度计,然后加起来看看
不管温度变化大不大,都要例行检查
二进制警报器(聪明保安):
给每个房间装了个"显著变化报警器":
房间A:温度变化超过64度才叫我
房间B:温度变化超过64度才叫我
...
当某个房间温度跳了很多(比如从30度突然到95度),报警器响了
你跑去检查,发现总和快超了,就把报警器调灵敏:
现在温度变化超过32度就叫你
如果还觉得危险,就调到16度、8度...直到1度
关键:大部分时间你在喝茶,只有真正需要时才工作!
简单来讲就是设置一个阀值 \(h\),这个阀值是运用于每一个位置的。如果有一个点超过了这个阀值(\(2^h\))的倍数,那就得注意了。
然后,我们检查一下,如果发现某项限制里面即使都不报警的前提下总和超过 \(v\),那么将 \(h\) 降低 \(1\)。
非常巧妙的方法!不愧是 AK IOI 的选手!
