在给定总和下计算最小子集 [英] Calculating Minimal Subset With Given Sum

问题描述

我在Scala中遇到问题，这是任务说明的摘要：

I was doing a problem in Scala and this is the summary of the task statement:

有一个整数列表（长度N，0 ＜N ＜10 ^ 5）和另一个整数S（0 ＜S ＜10 ^ 15）。您需要找到给定列表的最小子集的最小大小，该最小子集的元素之和（在子集中）大于或等于S。

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.

输入如下：

4

4 12 8 10

4

4 13 30 100

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

上面示例的输出：

1

2

3

-1

Output for above example:
1
2
3
-1

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

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。

Here's what I tried: The elements selected do not matter. So I sorted the list of given integers largest first. Then I selected the first one checked if its greater than S. If not, I selected the second element also, and so on until the sum becomes greater than or equal to S.

该算法有效，我得到了许多正确的测试用例。但是我已经超过了时限。如果您可以指出如何更快地执行此操作，或者有更好的方法来执行此操作，将不胜感激。

This algorithm works and I got many test cases correct. But I'm getting Time Limit Exceeded for some. If you can point out how I could make this faster or if there's a better way to do this, it would be much appreciated.

我的代码（Scala）：

My code (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)
      }
    }
  }
}

推荐答案

不需要完整的金额列表，而使用 BigInt 无论如何都是浪费-长可以解决d到9.2e18，那么您将只出现1e15。 （实际上，我认为选择1e15是为了使 Double 都可以保留答案而不会损失精度。）

Making a full list of sums is unnecessary, and using BigInt is wasteful regardless--a Long can hold up to 9.2e18, and you are promised that only 1e15 is going to appear. (In fact, I think 1e15 was chosen so that even a Double can hold the answer without loss of precision.)

此外，您可以对基元使用快速排序，而不是像 _>这样的慢速通用排序。 _ 最终将整数装箱。因此：

Also, you can use a fast sort on primitives rather than a slow generic sort like _ > _ which ends up boxing the integers. So:

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

然后，使用累加器（ Long 会做）：

Then, use an accumulator (Long will do):

var sum = 0L

并使用while循环搜索答案，切记最大的元素是最后一个，所以您想从头开始：

and search for the answer with a while loop, keeping in mind that the biggest elements are last so you want to start at the end:

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

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

Now you just need to check if you succeeded or failed before running out of elements:

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

这篇关于在给定总和下计算最小子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！