[CCO2022] Rainy Markets (未完成代码)
算法
先贪心判定最劣情况能否符合题目要求, 即能买伞的全部去买伞, 然后在按照 \(u_i = 0\) 的贪心策略(即尽量向左的填人数), 于是可以判断是否有可行解
-
不可行
显然直接输出 NO -
可行
考虑 \(\rm{Subtast } 1\)
显然为向左贪心
考虑 \(\rm{Subtast } 2, 3, 4\)
先按照 \(\rm{Subtast } 1\) 的方式进行贪心, 发现还有余下的人
分析原因: 先前的市场, 一些可以买雨伞的人挤占了这些人的空间, 导致这些人没地方走
于是想办法维护 \(u_i \neq 0\) 的序列连通性, 然后每次超出了就往前找到第一个可以买雨伞的地方, 腾出空间, 这是 \(O(\log n)\) 的
然后剩下的同 \(\rm{Subtast } 1\)
代码
后补
总结
从特殊到一般的一种实现方式是
先用一种方法特殊处理, 转化成特殊情况
如果一道题有多种情况, 先判定情况有助于分析问题
寻找一些特殊性质的序列连通性可以使用并查集解决