Chtholly可爱捏
我们先考虑如果\(n \cdot c \leq m\)我们要怎么做，我们可以发现里面一定存在一个数出现了\(\geq \lceil \frac{m}{c} \rceil\)，不妨设这个数为\(x\)，因此我们只需要把所有数都改成\(x\)就可以了
等等好像不对，我们一开始并不知道这个数是什么，我们只能一个一个加，这要怎么办呢？
于是我们想到了一个策略：对于当前读入的数\(k\)，在\(a_i\)中从左到右便利每一个数，找到最左边的\(a_i > k\)或\(a_i = 0\)的位置，并把这个位置修改成\(k\)
这个做法是可以保证构造出长度\(\geq \lceil \frac{m}{c} \rceil\)的解的，理由如下：
-
若读入的\(k = x\)，则构造的长度显然\(\geq \lceil \frac{m}{c} \rceil\)
-
若读入的\(k > x\)，则若\(k\)出现在\(x\)后面，只会让答案增加而不减少；反之，他会被后面的\(x\)覆盖掉，构造的长度显然\(\geq \lceil \frac{m}{c} \rceil\)
-
若读入的\(k < x\)，则若\(k\)出现在\(x\)前面，只会让答案增加而不减少；反之，他会替换掉最前面一个\(x\)，对长度没有影响，构造的长度显然\(\geq \lceil \frac{m}{c} \rceil\)
因此我们只需要按照这个构造方案就必然可以构造一个长度\(\geq n\)的答案
我们再回到原问题，考虑\(n \cdot \lceil \frac{c}{2} \rceil \leq m\)我们要怎么处理
我们使用同样的思路，把数分成\(\leq \lfloor \frac{c}{2} \rfloor\)和\(> \lfloor \frac{c}{2} \rfloor\)部分，分别处理，同理可以证明正确性：
设\(\leq \lfloor \frac{c}{2} \rfloor\)的数的个数为\(k\)，则\(> \lfloor \frac{c}{2} \rfloor\)的个数为\(m-k\)
容易推出：
\[\lceil \frac{k}{ \lfloor \frac{c}{2} \rfloor } \rceil + \lceil \frac{m-k}{ \lfloor \frac{c}{2} \rfloor } \rceil \geq \lceil \frac{2k}{c} \rceil + \lceil \frac{2(m-k)}{c} \rceil \geq \lceil \frac{2m}{c} \rceil \geq n \]最终复杂度\(O(n^2)\)，用数据结构可以优化到\(O(nlogn)\)(但没必要)
标签：lfloor,Chtholly,lceil,frac,CF896B,geq,rfloor,Ithea,rceil From： https://www.cnblogs.com/fox-konata/p/17688869.html