CF-Educational Codeforces Round 44 (Rated for Div. 2)-E-Pencils and Boxes

ACM模版

描述

题解

这个题没有想象中那么难，和 C$C$ 题有些可借鉴之处。

在排序之后，进行贪心。首先我们考虑如果要满足题意，一共需要分为 nk$\frac{n}{k}$ 组，因为只有组数最多才能保证每堆的铅笔数尽量少，继而可以尽量保证每组的差值小于等于 d$d$，如果每组第一个数是 pos$pos$，那么这组数最大不会超过 a[pos]+d$a[pos]+d$，但是我们并不能将所有小于等于它的铅笔都分配给它，这里我们采用的贪心策略是保证剩余的铅笔数可以分配给剩余的组的情况下，尽量给目前的组进行分配。这样不断进行贪心，一组一组分配，直到组数为 0$0$ 且铅笔分配完，说明结果为 YES$YES$，反之，为 NO$NO$。

---

羞耻的分割线：
感谢评论区大佬给予及时的指正，上述思路会 WA78（代码 One）$WA78（代码One）$，这个题的正解应该是 dp$dp$，有的人用 dp +$dp+$ 树状数组给 A$A$ 掉的，不过，不用树状数组也是完全可以的。接下来讲一下不用树状数组的解法，这个解法是从看大佬的代码（代码 Two$Two$）学到的。

首先，必须排序，然后我们设置一个 pos[i]$pos[i]$ 表示 i∼ptr−1$i\sim ptr-1$ 差值小于等于 d$d$ 的最大 ptr$ptr$ 值，以此给 i$i$ 初始化好它所能分组的最远边界；接着我们设置 ans[i]$ans[i]$ 表示以 i$i$ 作为下一个分组起点的情况数，令 ans[0]=1$ans[0]=1$ 表示从 0$0$ 作为起点的情况有 1$1$ 种，这里十分好理解，因为数据从 0$0$ 下标开始存，那么如果 ans[n]$ans[n]$ 大于 0$0$ 说明从 n$n$ 为起点开始新的分组的情况数大于 0$0$，也就意味着前边 0∼n$0\sim n$ 是可以完美分组的。

这里，我们还需要引入一个 dif[]$dif[]$ 来控制对于当前起点 i$i$ 的下一个分组的起点的控制范围，首先，我们知道对于 i$i$ 作为起点时，他的终点范围是 i+k−1∼pos[i]−1$i+k-1\sim pos[i]-1$，那么下一个起点 i′$i^{\prime }$ 的范围自然就是 i+k∼pos[i]$i+k\sim pos[i]$，这也是为什么可以用树状数组解的原因，我们需要将这个范围都统一进行标记，不过这里存在一个技巧可以省去树状数组，那就是我们只需要设置 dif[i+k]++$dif[i+k]++$ 与 dif[pos[i]+1]−−$dif[pos[i]+1]--$ 两个边界就可以了，然后结合 ans[i]=ans[i−1]+dif[i]$ans[i]=ans[i-1]+dif[i]$，如此运作，在遍历到 i+k∼pos[i]$i+k\sim pos[i]$ 范围时，dif[i+k]++$dif[i+k]++$ 的作用就可以持续有效，等价于后续遍历的位置全部都自增了，待到遍历至 pos[i]+1$pos[i]+1$ 时，dif[i+k]++$dif[i+k]++$ 与 dif[pos[i]+1]−−$dif[pos[i]+1]--$ 便相互抵消了，保证只有在 i+k∼pos[i]$i+k\sim pos[i]$ 范围内自增效果有效。如此这般，便可以完美省略树状数组的需求。

以上只是个人拙见，如另有高见，敬请指点一二！

代码

代码 One：

//  WA78
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 5e5 + 10;

int n, k, d;
int a[MAXN];

int main()
{
    cin >> n >> k >> d;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a, a + n);

    int m = n / k, pos = 0;

    while (m && pos < n)
    {
        m--;
        int mx = a[pos] + d;
        while (pos < n && (n - pos > m * k) && a[pos] <= mx)
        {
            pos++;
        }
    }

    if (m == 0 && pos == n)
    {
        printf("YES\n");
    }
    else
    {
        printf("NO\n");
    }

    return 0;
}

代码 Two：

//  AC1
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAXN = 5e5 + 10;

int n, k, d;
int a[MAXN], pos[MAXN];
int ans[MAXN], dif[MAXN];

int main()
{
    scanf("%d%d%d", &n, &k, &d);

    for (int i = 0; i < n; i++)
    {
        scanf("%d", a + i);
    }
    sort(a, a + n);

    int ptr = 0;
    for (int i = 0; i < n; i++)
    {
        while (ptr < n && a[ptr] - a[i] <= d)
        {
            ptr++;
        }
        pos[i] = ptr;   //  i ~ ptr - 1 差值小于等于 d 且 ptr 最大
    }

    ans[0] = 1;         //  i 作为下一个分组的起点的情况数
    dif[1] = -1;        //  控制下一个起点的范围，如果当前 i 为起点，那么 i + k 可以为下一个起点，
                        //  换言之，对于 i 为起点的情况，他的终点必须在 i + k - 1 ~ pos[i] - 1 这个范围
                        //  所以 i + k ~ pos[i] 可以作为下一个起点，而 pos[i] + 1 则不能作为下一个起点
                        //  因为 ans[i] = ans[i - 1] + dif[i]，所以只需要设置
                        //  dif[i + k]++ 与 dif[pos[i] + 1]-- 即可
    for (int i = 0; i < n; i++)
    {
        if (i)
        {
            ans[i] = ans[i - 1] + dif[i];
        }

        if (ans[i] == 0)
        {
            continue;
        }
        if (pos[i] - i < k)
        {
            continue;
        }

        dif[i + k]++;
        dif[pos[i] + 1]--;
    }

    ans[n] = ans[n - 1] + dif[n];

    puts(ans[n] ? "YES" : "NO");

    return 0;
}