1

我正在尝试解决 scala 中 codechef 的翻转硬币问题。问题陈述如下：

桌上有 N 个硬币，编号从 0 到 N - 1。最初，每个硬币都是反面朝上的。您必须执行两种类型的操作： 1) 翻转编号在 A 和 B 之间的所有硬币。这由命令“0 A B”表示 2) 回答编号在 A 和 B 之间的硬币有多少是正面朝上的。这由命令“1 A B”表示。输入：第一行包含两个整数，N 和 Q。接下来的 Q 行中的每一行都是上面提到的“0 A B”或“1 A B”的形式。

输出：为“1 A B”形式的每个查询输出 1 行，其中包含相应查询所需的答案。

样本输入：

 4 7
1 0 3
0 1 2
1 0 1
1 0 0
0 0 3
1 0 3 
1 3 3

样本输出：

0
1
0
2
1

约束：1 <= N <= 100000 1 <= Q <= 100000 0 <= A <= B <= N - 1

以最简单的方式，我正在考虑在 scala 中初始化一个 Ints 数组，如下所示：

 var coins = new Array[Int](1000)

如果我遇到命令 0 AB，我将简单地将 A 的索引设置为直到 B+1 为 1，如下所示：

 for(i <- 5 until 8){
      coins(i) = 1
    }

如果我遇到命令 1 AB，我将从 A 到 B+1 取出数组的一个切片，并计算给定切片中 1 的数量，我将按如下方式执行：

val headCount = coins.slice(5,8).count(x => x == 1)

看起来这个操作在最坏的情况下需要 O(n) ，显然这可以优化为在对数时间内解决。

有人可以指出我在这里可能做错了什么以及如何以最佳方式解决这个问题。

谢谢

4

2 回答 2

2

这些天我对 scala 了解不多，但我可以为关于 O(log(n)) 的更一般的问题提出一个答案。通常这样的算法使用树，我认为你可以在这里这样做。

如果您构建一个平衡树，硬币作为叶子，那么您可以在每个节点中存储硬币的总数和该节点下方叶子中的正面数量。您可以想象翻转硬币的代码从节点信息中计算出要访问的叶子，并在 O(n) 时间内工作（您仍然需要翻转硬币）。但是如果翻转代码也更新了节点数据，那么头的数量将是 O(log(n)) 因为您可以使用节点信息 - 您不需要去叶子。

这样一个命令给你 O(n)，另一个命令给你 O(log(n))。

但你可以做得更好。我认为你也可以进行翻转操作 O(log(n))。为此，您将向每个节点添加一个“翻转”标志。如果设置，则该点以下的所有节点都被翻转。有一些记账细节，但总体思路是有的。

如果您将此得出合乎逻辑的结论，那么您实际上不需要存储叶子，至少在开始时是这样。您只需在处理命令时添加具有所需详细程度的节点。此时，您基本上有了评论中提到的区间树。

于 2012-05-01T22:50:26.273 回答
0

一种简洁的建模方法是作为BitSet，其中集合中的整数值表示棋盘上正面的索引。然后你可以在这样的范围内翻转硬币：

def flip(coins: BitSet, a: Int, b: Int) = coins ^ BitSet(a to b: _*)

您可以类似地计算范围内的正面数：

def heads(coins: BitSet, a: Int, b: Int) = (coins & BitSet(a to b: _*)).size

或者（可能更快）可变java.util.BitSet版本：

import java.util.BitSet

def flip(coins: BitSet, a: Int, b: Int) { coins.flip(a, b + 1) }
def heads(coins: BitSet, a: Int, b: Int) = coins.get(a, b + 1).cardinality

这不一定是最佳的，但它是一种相当有效的方法，因为您只是在翻转位。

于 2012-05-01T21:24:54.797 回答