0

我正在尝试解决定义如下的问题：

糖果由从 1 到 1e6 的数字表示。如果一个人有 1 到 k 个糖果，则称他有 k 个糖果。

例如，如果一个人买了糖果 1、2 和 6，那么他有一套 2 颗糖果

给定 2 种类型的操作：吃 x 和买 x，其中 x 代表糖果数量。购买 x 只会将 x 的数量增加 1。吃 x 只会使 x 的数量减少 1。

对于每个操作，回答问题，我现在拥有的那套糖果的大小是多少？

我正在努力寻找最有效的方法来做到这一点。我想到的解决方案描述如下：

让 count[i] 定义大小为 1 - N 的数组，其中 N 是可能的最大糖果数。count[i] 存储我目前拥有的编号为 i 的糖果的数量。

让 Fenwick[i] 数组大小为 1 - N，其中 N 是最大可能的糖果数。这个数组用于构建一个 fenwick 树来存储我收藏中糖果的累积总和。此累积和不使用计数数组。累积总和计数 1 的数量（每个 1 表示我的收藏中存在糖果 x）。例如，如果我有一组 5 颗糖果，那么从 1 到 5 的累积总和是 5。如果有一组 10 颗糖果，那么从 1 到 10 的累积总和是 10...

对于购买操作，如果我的收藏中还没有糖果 x，则从索引 x 开始的累积总和加 1（这由 fenwick 树处理）。否则，我将只执行 count[x]++

对于eat 操作，执行count[x]--。如果 count[x] 现在为 0，则从索引 x 开始的累积总和减 1（这由 fenwick 树处理）。

现在解决了插入和删除的部分。困难的部分是如何获取当前集合中的糖果集的大小。

我尝试在 Fenwick 树中查询最大索引 i，从 1 到 i 的累积总和等于 i，同时每次以 2 的幂递增查询索引。

我采用作为有效糖果集合的最大索引 j 和作为无效糖果集合的最小索引 k。然后从 j 循环到 k，在每次迭代时查询 fenwick 树。一旦循环遇到无效集合，中断并输出答案。

在我看来，这会奏效。但是，这肯定不是一种有效的方法。有人能启发我更好的解决方案吗？提前致谢。

编辑（解决方案）：

我的插入和删除方法是正确的。只是我以不正确的方式搜索糖果的集合。在这种情况下，我们想要最大的数 x，其中 query(x) = x（query(x) 给出从 1 到 x 的累积和）。所以我们可以使用二分查找来找到x的最大有效值（query(x) = x）。为了实现这一点，我们只需要保留一个额外的变量来跟踪 x 的最后一个值，其中 query(x) 给出了一个有效的集合。

解的复杂度：O(log^2(N))

4

1 回答 1

1

这通常是二叉树结构。

为简单起见，让我们说糖果的索引范围从0到2^k - 1某个整数k。然后每时每刻都用16数字表示状态，c[0]to c[2^k - 1]，其中c[i]是糖果的数量i。

我们构造一棵二叉树如下：根节点P(0, 2^k)代表整个区间[0, 2^k)；对于每个P(a, b)这样的节点b - a > 1，构造两个子节点P(a, (a + b)/2)和P((a + b)/2, b)。

设为区间 中p(a, b)的最小值。显然我们有：c[i]i[a, b)

  • p(a, a + 1) = c[a];

  • p(a, b) = min{p(a, (a + b)/2), p((a + b)/2, b)}如果b - a > 1.

构建了这个数据结构后，对于每个操作（加一或减一），我们可以O(k)从下到上逐步更新数据。此外，还可以逐步确定糖果组的大小O(k)。

数据结构示例：

让我们看一下案例k = 3，这样就有c[0]了c[7]。例如：

c[0 .. 7] = {1, 3, 0, 4, 3, 2, 8, 1}

然后树结构如下所示：

p(0, 8) = 0
|- p(0, 4) = 0
|  |- p(0, 2) = 1
|  |  |- p(0, 1) = 1
|  |  |_ p(1, 2) = 3
|  |_ p(2, 4) = 0
|     |- p(2, 3) = 0
|     |_ p(3, 4) = 4
|_ p(4, 8) = 1
   |- p(4, 6) = 2
   |  |- p(4, 5) = 3
   |  |_ p(5, 6) = 2
   |_ p(6, 8) = 1
      |- p(6, 7) = 8
      |_ p(7, 8) = 1

现在假设我们添加1到 number c[2]，它 beomes 1，那么我们只需要更新数字p(2, 3), p(2, 4), p(0, 4), p(0, 8)。

于 2016-10-23T13:54:43.030 回答