自动搬运

查看原文

来自洛谷，原作者为

	y3kkc 肉可往，我亦可往

搬运于2025-08-24 22:35:11，当前版本为作者最后更新于2023-08-24 19:01:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

见洛谷。

分析

暴力很好想。

直接暴力枚举第 $i$ 天，计算这天贡献，更新答案。

当天数大于 ${\textstyle \max_{i=1}^{i\le n}}v_i$ 后，各个平均数为 $0$，即为上界。

很显然会被卡到 $10^{10}$。

不难发现枚举 $i$ 时，会出现 $\left \lfloor \frac{a_j}{i} \right \rfloor$ 相等的情况。

我们对于一个 $\left \lfloor \frac{a_j}{i} \right \rfloor$，如何快速找到下一个 $i = k$ 使得 $\left \lfloor \frac{a_j}{i} \right \rfloor \ne \left \lfloor \frac{a_j}{k} \right \rfloor$？

这便是数论分块的板子，这里不过多介绍，还不懂的同学可去 OI Wiki 上学习。

我们对于每个 $\left \lfloor \frac{a_j}{i} \right \rfloor$，快速找到它的下一个 $k$，对于所有的 $k$ 取个最小值，就可做到不重不漏地枚举状态。

温馨提示：这题有点卡常，需要一定卡常技巧才能过。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 105, inf = 0x3f3f3f3f;
int n, a[N], ans[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + n + 1);
    memset(ans, -1, sizeof ans);
    for (int i = 1; i <= a[n] + 1; i++) {
        int sum = 0, k = inf;
        for (int j = 1; j <= n + 1; j++) {
            if (j == n + 1 || a[j] / i != a[j - 1] / i) {
                if (ans[sum] == -1)
                    ans[sum] = i;
                ans[sum] = min(ans[sum], i);
                sum = 0;
            }
            sum++;
        }
        for (int j = 1; j <= n; j++) {
            if (a[j] / i)
                k = min(k, a[j] / (a[j] / i));
        }
        i = k;
    }
    for (int i = 1; i <= n; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

总结

• 数论分块的板子吧，也可对于这种向下取整的枚举我们就应该要想到数论分块的。