c++ - 将数组分成两组？

Question

我有一个0..N-1的数组W

我需要将它们分成两组:说 K 和 N-K 元素。

但条件是:sum(N-K) - sum(K) 应该是最大值。

我该如何处理？

我试过这样做:对数组进行排序 - std::sort(W,W+N)，然后:

for(int i=0; i<K; ++i) less+=W[i];
for(int i=K; i<N; ++i) more+=W[i];

然后 more-less

但我认为这不是最佳方式，或者在某些情况下甚至可能是错误的。

谢谢。

更新:

我们必须从 W 中选择 K 个元素，使得 sum(k elements) 和 sum(remaining elements) 之间的差异 是最大值。

Answer 1

编辑:请注意，在您发布的问题中，您似乎期望 sort 从高到低排序。 std::sort 和 std::nth_element 都将低位元素放在第一位。我已将下面的答案中的 K 替换为 (N-K) 以更正该问题。

更新后编辑:执行以下两次，一次用于K，一次用于(N-K)。选择最佳答案。

比 std::sort 更优化的是 std::nth_element为了您的目的。

std::nth_element( W, W+(N-K), W+N );

您对 std::sort 的使用将使用 O(n log n) 复杂度来对您的两个集合中的所有元素进行排序，这是您不需要的。

std::nth_element 将使用 O(n) 复杂度来分区而不完全排序。

注意:您的 for 循环也可以替换为 std::accumulate

less = std::accumulate( W, W+(N-K), 0 );
more = std::accumulate( W+(N-K), W+N, 0 );