0x0–租借教室 洛谷p1083 (差分&二分)

最开始用暴力，时间超时，只能拿到60分：

分析了一下超时的原因：时间复杂度是O(n*m) 当n m都是题目中的最大值10^6时，总的处理次数为10^12，时间限制1s，远大于一秒处理次数10^8。

因此可以考虑用差分的方法来判断第i个请求是否满足，时间复杂度仅为O(n+m),并且最后用一个二分查找来判断到哪一个之前满足，总的时间复杂度为O( [log(m)] * (n+m) ) 当m很大时，时间复杂度显著降低。下面是更新后的代码：

0x01–跳石头 洛谷p2678

本题第一反应是用dfs做，类似于昨天的那道选数的题目，尝试了dfs未果，因为时间复杂度太高。选数的那题N最大值为20，这题N最大值为50000，时间复杂度为O(N^M)，直接爆炸了。

如果考虑用bfs,不仅要记录每个节点的步数（第几个移除的石块）并且每个组合都要对差分数组进行赋值、操作，时间复杂度依旧爆炸。（而且程序也很复杂）

这道题并不适合用dfs,bfs，数据量太大了。

二分法可轻松完美解决这道题

顺便学了一手快读。

0x02–逛画展 洛谷p1638 （二分&滑动窗口）