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

I have this homework:

我有这个功课:

Given an array consisting of N integers, you are required to print the minimum contiguous sum that can be obtained by performing at most K swaps. During a swap any 2 elements of the given array could be swapped.

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

I tried this

我试过这个

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;
}

It will give the minimum sum without any swappings, but how can I improve in no more than K swaps?

它会给出最小的金额而不需要任何交换,但是如何在不超过K个交换的情况下进行改进?

2 个解决方案

#1

import java.io.BufferedReader;
import java.io.InputStreamReader;

import java.util.Collections;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;


class TestClass {

       static Scanner scanner;
        public static void main(String args[] ) throws Exception {


        scanner=new Scanner(System.in);
        int T=scanner.nextInt();

        while(T>0){
        int N=scanner.nextInt();
        int K=scanner.nextInt();
        int[] array=new int[N];
         for(int i=0;i<array.length;i++)
         {
            array[i]=scanner.nextInt();
        }


         System.out.println(findingMinimumSumSubarray(array, K));

            T--;
        }


    }

    public static int findingMinimumSumSubarray(int[] values, int k) {
     int N = values.length;
     int res = values[0]; 
     for (int L = 0; L < N; L++) {
         for (int R = L; R < N; R++) {
             List<Integer> A= new ArrayList<Integer>();
             List<Integer> B = new ArrayList<Integer>(); 
             int ashu = 0; 
             for (int i = 0; i < N; i++) {
                 if (i >= L && i <= R) {
                  A.add(values[i]);
                     ashu += values[i];
                 } else {
                     B.add(values[i]);
                 }
             }

             Collections.sort(A);

             Collections.sort(B);
             Collections.reverse(B);
             res = Math.min(res, ashu); 
             for (int t = 1; t <= k; t++) {

                 if (t > A.size() || t > B.size()) break;

                 ashu -= A.get(A.size() - t);
                 ashu += B.get(B.size() - t);
                 res = Math.min(res, ashu);
             }
         }
     }
     return res;
 }
}

#2

You solution is not correct even without swap.

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

Test: [-1, 2, -1]. Your answer on this test is -2. Correct answer: -1

测试:[-1,2,-1]。你在这个测试中的答案是-2。正确答案:-1

I hope that my solution is not best and there is better approach.

我希望我的解决方案不是最好的,并且有更好的方法。

Simple O(N^3) complexity solution.

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

Let's assume that our final minimum contiguous segment will be [L, R] for some 0 <= L <= R < N. Now we have two multiset: A and B. A - multiset with "inner" numbers (numbers that are inside range [L, R]) and B - multiset with "outer" numbers (numbers that are outside of range [L, R]). Out goal is to minimize sum of numbers in A - sum(A). Making swap inside A or B is meaningful, because it will not affect to sum(A). We can swap one element from A with other element in B. We have no more than K swaps, and it means that no more than K elements in A will be swapped with no more than K elements in B. To reach minimum value of sum(A) we will take some maximum elements in A and swap them with minimum elements in B. For example:

假设我们的最终最小连续段将是[L,R],对于某些0 <= L <= R 现在我们有两个多重集:a和b.>

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

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

• We can make 0 swaps, A = {-3, -3, -1, 2}; B = {-4, 1, 3, 6}; then sum(A) == -3

我们可以进行0次交换,A = { - 3,-3,-1,2}; B = { - 4,1,3,6};总和(A)== -3

• We can make 1 swaps, A = {-3, -3, -1, -4}; B = {2, 1, 3, 6}; then sum(A) == -11

我们可以进行1次交换,A = { - 3,-3,-1,-4}; B = {2,1,3,6};总和(A)== -11

• We can make 2 swaps, A = {-3, -3, 1, -4}; B = {2, -1, 3, 6}; then sum(A) == -9

我们可以进行2次交换,A = { - 3,-3,1,-4}; B = {2,-1,3,6};总和(A)== -9

Answer is sum(A) == -11

答案是总和(A)== -11

For range [L, R] we can get minimum possible sum. To obtain answer for our initial problem we will iterate over all possible ranges [L, R]. 0 <= L <= R < N

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

Naive implementation. O(N^3logn) complexity.

天真的实施。 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;
}

Optimization

Let's assume that for the range [L, R] we already know sorted set A and reverse sorted set B. When we will compute for the range [L, R + 1] exactly one element will be deleted from B and inserted in A(this number is exactly values[R+1]). C++ has containers set and multiset that can allow us to insert and remove in O(log) time and iterate in O(n) time. Other programming languages also has same containers (in java it is TreeSet/SortedSet). So when we move R to R+1, we will make some simple queries to multiset(insert/remove).

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

O(N^3) solution.

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;
}