其实就是求[∑i=1n{d×⌈aid⌉−ai}<=k]\Big[\displaystyle \sum_{i=1}^{n} \{d\times \lceil \frac{a_i}{d} \rceil- {a_i} \} <=k \Big][i=1∑n{d×⌈dai⌉−ai}<=k]其中d的最大值
先排序
考虑暴力的情况,枚举答案是1~a[n] ,然后判定,
然后想二分,但是发现 不满足单调性,所以不行。
考虑如何优化这个枚举过程。
首先考虑这个式子
∑i=1n{d×⌈aid⌉−ai}<=k∑i=1nd×⌈aid⌉−∑i=1nai<=kd×∑i=1n⌈aid⌉<=k+∑i=1naid<=k+∑i=10ai∑i=1n⌈aid⌉\displaystyle \sum_{i=1}^{n} \{d\times \lceil \frac{a_i}{d} \rceil- {a_i} \} <=k \\ \displaystyle \sum_{i=1}^{n} d\times \lceil \frac{a_i}{d} \rceil-\displaystyle \sum_{i=1}^{n} {a_i} <=k \\ \displaystyle d\times \sum_{i=1}^{n} \lceil \frac{a_i}{d} \rceil<=k+\displaystyle \sum_{i=1}^{n} {a_i} \\ d<= \dfrac{k+\displaystyle\sum_{i=1}^{0}a_i}{\displaystyle \sum_{i=1}^{n} \lceil \frac{a_i}{d} \rceil} \\i=1∑n{d×⌈dai⌉−ai}<=ki=1∑nd×⌈dai⌉−i=1∑nai<=kd×i=1∑n⌈dai⌉<=k+i=1∑naid<=i=1∑n⌈dai⌉k+i=1∑0ai
然后考虑分段枚举d的时候对于aid\frac{a_i}{d}dai只有sqrtsqrt{}sqrt种情况, 不知道的话 可以先做做这道题<–戳这里
于是枚举ddd即可,考虑d<=k+∑i=10ai∑i=1n⌈aid⌉d<= \dfrac{k+\displaystyle\sum_{i=1}^{0}a_i}{\displaystyle \sum_{i=1}^{n} \lceil \frac{a_i}{d} \rceil} \\d<=i=1∑n⌈dai⌉k+i=1∑0ai这个限制的同时不断维护最大值
注意d对每个a[i] 分段枚举的时候要满足所有的a[i] ,所以要取最小的.
复杂度O(n×max{a[x]∣x∈[1,n]})O(n\times \sqrt{max\{a[x] \Big|x\in[1,n]\} })O(n×max{a[x]x∈[1,n]})