通过执行最多K个交换可以获得的最小连续总和

Question

我有这个功课:

给定一个由N整数组成的数组,您需要打印通过执行最多K交换可以获得的最小连续总和.在交换期间,可以交换给定数组的任何2个元素.

我试过这个

int currentSum = 0;
int currentMin = 0;

for (int j = 0; j < input.Length; j++)
{
    if (input[j] >= 0)
        continue;
    currentSum += input[j];

    if (currentMin > currentSum)
        currentMin = currentSum;
}

它会给出最小的金额而不需要任何交换,但我怎样才能在不超过K掉期的情况下进行改进？

Answer 1

即使没有交换，您的解决方案也是不正确的。

测试：[-1, 2, -1]。您在此测试中的答案是 -2。正确答案：-1

我希望我的解决方案不是最好的，还有更好的方法。

简单的 O(N^3) 复杂度解决方案。

让我们假设我们的最终最小连续段将是 [L, R] 对于某些 0 <= L <= R < N。现在我们有两个多重集：A 和 B。A - 具有“内部”数字（内部的数字）的多重集范围 [L, R]) 和 B - 具有“外部”数字（范围 [L, R] 之外的数字）的多重集。我们的目标是最小化 A 中的数字之和 - sum(A)。在 A 或 B 内部进行交换是有意义的，因为它不会影响 sum(A)。我们可以将 A 中的一个元素与 B 中的其他元素交换。交换次数不超过 K 个，这意味着 A 中不超过 K 个元素将与 B 中不超过 K 个元素交换。要达到 sum 的最小值(A) 我们将取 A 中的一些最大元素并将它们与 B 中的最小元素交换。例如：

A = {-3, -3, -1, 2}; B = {-4, 1, 3, 6}; K = 2；

• 我们可以进行 0 次交换，A = {-3, -3, -1, 2}；B = {-4, 1, 3, 6}; 那么 sum(A) == -3
• 我们可以进行 1 次交换，A = {-3, -3, -1, -4}；B = {2, 1, 3, 6}; 那么 sum(A) == -11
• 我们可以进行 2 次交换，A = {-3, -3, 1, -4}；B = {2, -1, 3, 6}; 那么 sum(A) == -9

答案是 sum(A) == -11

对于范围 [L, R]，我们可以获得最小可能的总和。为了获得我们最初问题的答案，我们将迭代所有可能的范围 [L，R]。0 <= L <= R < N

幼稚的实施。O(N^3logn) 复杂度。

int get_minimum_contiguous_sum(vector <int> values, int k) {
    int N = values.size();
    int ans = values[0]; // initializing with any possible sums
    for (int L = 0; L < N; L++) {
        for (int R = L; R < N; R++) {
            vector <int> A, B; // our "inner" and "outer" sets
            int suma = 0; // will store initial sum of elements in A
            for (int i = 0; i < N; i++) {
                if (i >= L && i <= R) {
                    A.push_back(values[i]);
                    suma += values[i];
                } else {
                    B.push_back(values[i]);
                }
            }
            // Sorting set A in non-descending order
            sort(A.begin(), A.end());
            // Sorting set B in non-increasing order
            sort(B.begin(), B.end());
            reverse(B.begin(), B.end());
            ans = min(ans, suma); // Updating answer with initial state
            // Iterating number of swaps that we will make
            for (int t = 1; t <= k; t++) {
                // if some of two sets contain less than t elements
                // then we cannot provide this number of swaps
                if (t > A.size() || t > B.size()) break;
                // Swapping t-th maximum of A with t-th minimum of B
                // It means that t-th maximum of A subtracts from suma
                // and t-th minimum of B added to suma
                suma -= A[A.size() - t];
                suma += B[B.size() - t];
                ans = min(ans, suma);
            }
        }
    }
    return ans;
}

优化

假设对于范围 [L, R]，我们已经知道排序集 A 和反向排序集 B。当我们计算范围 [L, R + 1] 时，恰好有一个元素将从 B 中删除并插入到 A(这个数字正好是值[R+1]）。C++ 具有容器集和多重集，可以让我们在 O(log) 时间内插入和删除，并在 O(n) 时间内迭代。其他编程语言也有相同的容器（在java中是TreeSet/SortedSet）。因此，当我们将 R 移动到 R+1 时，我们将对多重集（插入/删除）进行一些简单的查询。

O(N^3) 解。

int get_minimum_contiguous_sum(vector <int> values, int k) {
    int N = values.size();
    int ans = values[0]; // initializing with any possible sums
    for (int L = 0; L < N; L++) {
        // "inner" multiset
        // Stores in non-increasing order to iterate from beginning
        multiset<int, greater<int> > A;
        // "outer" multiset
        // multiset by defaul stres in non-decreasing order
        multiset<int> B;
        // Initially all elements of array in B
        for (int i = 0; i < N; i++) {
            B.insert(values[i]);
        }
        int suma = 0; // Empty set has sum=0
        for (int R = L; R < N; R++) {// Iterate over all possible R
            // Removing element from B and inserting to A
            B.erase(B.find(values[R]));
            A.insert(values[R]);
            suma += values[R];
            ans = min(ans, suma);
            __typeof(A.begin()) it_a = A.begin();
            __typeof(B.begin()) it_b = B.begin();
            int cur = suma;
            for (int i = 1; i <= k; i++) {
                if (it_a != A.end() && it_b != B.end())
                    break;
                cur -= *it_a;
                cur += *it_b;
                ans = min(ans, cur);
                it_a++;
                it_b++;
            }
        }
    }
    return ans;
}