P8016 [COCI2013-2014#4] ČOKOLADE 题解

· · 题解

题意

见洛谷。

分析

暴力很好想。

直接暴力枚举第 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;
}

总结