前言
以一道绿结束今天的每日 \(\rm{C}\) 比较合理
思路
你发现假设分成大小为 \(s\) 的副牌, 只要满足
\[s \mid \sum_{i = 1}^{n} a_i \textrm{ and } \forall i \in [1, n], a_i \leq \frac{\sum_{i = 1}^{n} a_i}{s} \]即可
考虑贪心的买新牌, 每次只需要把小的补上去即可
也就是说, 在最初补满 \(a_i\) 之后, 以后每新买 \(n\) 张牌就会使得 \(\max a_i\) 加一
那么怎么实现
首先你计算出把 \(a_i\) 补满的花费 \(C\) , 简单分类讨论
\(k \leq C\)
这种情况下, 不管怎么填, \(\max a_i\) 固定
可以计算出 \(\sum a_i\) 的取值区间, 然后 \(\mathcal{O} (n)\) 判断最大的 \(k\) 使其符合要求
\(k > C\)
这种情况下稍微要复杂一点
首先同上计算, 然后令 \(k \gets k - C\)
你发现对于现在的 \(k\) , 每放 \(n\) 个就会使得 \(\max a_i\) 加一, 考虑 \(k\) 可以产生 \(\max a_i\) 的区间, 对于整段直接判断, 对于前后的小段你 \(\mathcal{O} (n)\) 检查即可
看完题解觉得自己是弱智
你考虑对于每一个 \(s\) 怎么判定
\(\sum_{i = 1}^{n} a_i < s \times \max a_i\)
显然的, 只要 \(\sum_{i = 1}^{n} a_i + k \geq s \times \max a_i\) 即可, 原因是当 \(\sum_{i = 1}^{n} a_i = s \times \max a_i\) 时, 一定是最优秀的补数同时满足以上两种条件
\(\sum_{i = 1}^{n} a_i \geq s \times \max a_i\)
只要 \([s - (\sum_{i = 1}^{n} a_i \textrm{ mod } s)] \textrm{ mod } s \leq k\) 即可
具体的, 你画画图可以发现, 去补的时候会在上面均匀的加几层, 虽然 \(\max a_i\) 发生了变化, 但是仍然满足条件
总结
一类贪心
注意一定要把思路弄得明白再去打代码, 然后也就是不要慌, 代码错了检查思路
注意根据问题复杂度简化思路, 不去考虑不影响答案的情况
不过这个题, 知道这类贪心的做法之后就简单了, 否则并不好想
这个贪心的思路其实就是构造方法的差别
具体一点就是能不能想到 这种方法 去构造