algorithm - 用给定的总和计算最小子集

Question

我在 Scala 中做题，这是任务语句的摘要:

There is a list of integers (of length N, 0 < N < 10^5) and another integer S (0 < S < 10^15). You are required to find the minimal size of the minimal subset of the given list of which the sum of elements (in the subset) is greater than or equal to S.

Input is given as below:
4
4 12 8 10
4
4 13 30 100

Output for above example:
1
2
3
-1

First line is length of array, the second is the array of integers (0 < A[i] < 10^9), the third is the number of test cases (0 < T < 10^5) and the fourth contains the S (for each test case).

这是我尝试过的:选择的元素无关紧要。所以我首先对给定整数列表进行排序。然后我选择第一个检查它是否大于 S。如果不是，我也选择第二个元素，依此类推，直到总和大于或等于 S。

这个算法有效，我得到了许多正确的测试用例。但是我遇到了一些 Time Limit Exceeded。如果您能指出我如何才能使它更快或者是否有更好的方法来做到这一点，我们将不胜感激。

我的代码(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
}