求给定和的极小子集

Question

我在Scala中做了一个问题，这是任务语句的摘要：

上述示例的输出:
1
2
3
-1

第一行是数组长度，第二行是整数数组(0

以下是我尝试的：选择的元素并不重要。所以我先对给定整数的列表排序最大。然后我选择了第一个元素，检查它是否大于S，如果不大于S，我也选择了第二个元素，依此类推，直到总和大于或等于S。

我的代码（Scala）：

object Solution {
  def main(args: Array[String]) {
    val n = readInt()
    val arr: Array[Long] = readLine().split(" ").map(_.toLong).sortWith(_ > _)

    val sums: Array[BigInt] = new Array(n)
    sums(0) = arr(0)
    for(i <- 1 until n) sums(i) = sums(i-1) + arr(i)

    val t = readInt()
    for(i <- 1 to t) {
      val s:BigInt = BigInt(readLong())
      if(sums(n-1) < s)
        println(-1)

      else {
        var i = 0
        while(sums(i) < s) i += 1
        println(i + 1)
      }
    }
  }
}

Answer 1

创建一个完整的和列表是不必要的，而且使用bigint无论如何都是浪费的--一个long最多可以容纳9.2e18，并且您被保证只会出现1e15。（事实上，我认为选择1E15是为了即使是double也能保持答案而不损失精度。）

此外，您可以对基元使用快速排序，而不是使用诸如_>_这样的慢速泛型排序，后者最终装箱整数。所以：

val arr = {
  val in = readLine().split(' ').map(_.toInt)
  java.util.Arrays.sort(in)
  in
}

然后，使用累加器(long即可）：

var sum = 0L

并使用while循环搜索答案,记住最大的元素是最后一个,所以您希望从结尾开始：

var i = arr.length-1
while (i >= 0 && sum < t) {
  sum += arr(i)
  i -= 1
}

现在您只需要在用完元素之前检查成功还是失败：

val answer = {
  if (i < 0) -1
  else arr.length - i - 1
}