somma contigui minimo che può essere ottenuto effettuando al massimo K swap

Question

ho questo lavoro:

Dato un array composto da N numeri interi, si sono tenuti a stampare la somma contigua minimo che può essere ottenuto dopo aver effettuato al massimo K swap. Durante uno scambio, è possibile scambiare qualsiasi 2 elementi dell'array dato.

Ho provato questo

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

Darà la somma minima senza swappings, ma come posso migliorare in non più di K swap?

Answer 1

La soluzione non è corretta anche senza scambio.

Test: [-1, 2, -1]. La tua risposta su questo test è -2. Risposta corretta: -1

Spero che la mia soluzione non sia la migliore e che ci sia un approccio migliore.

Soluzione di complessità semplice O (N^3).

Supponiamo che il nostro segmento contiguo minimo finale sarà [L, R] per qualche 0 < = L = R < < N. Ora abbiamo due multiset: A e B. A - Multiset con numeri "interni" (numeri che si trovano nell'intervallo [L, R]) e B - multiset con numeri "esterni" (numeri che non rientrano nell'intervallo [L, R]). Il nostro obiettivo è minimizzare la somma dei numeri in A - sum (A). Fare lo scambio all'interno di A o B è significativo, perché non influirà sulla somma (A). Possiamo scambiare un elemento da A con un altro elemento in B. Non abbiamo più di K swap, e significa che non più di K elementi in A saranno scambiati con non più di K elementi in B. Per raggiungere il valore minimo di somma (A) prendiamo alcuni elementi massimi in A e li scambiamo con elementi minimi in B. Ad esempio:

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

• Possiamo fare 0 swap, A = {-3, -3, -1, 2}; B = {-4, 1, 3, 6}; then sum (A) == -3
• Possiamo fare 1 swap, A = {-3, -3, -1, -4}; B = {2, 1, 3, 6}; then sum (A) == -11
• Possiamo fare 2 swap, A = {-3, -3, 1, -4}; B = {2, -1, 3, 6}; quindi somma (A) == -9

Risposta è somma (A) == -11

Per intervallo [L, R] possiamo ottenere minimo possibile somma. Per ottenere una risposta al nostro problema iniziale, itereremo su tutti i possibili intervalli [L, R]. 0 < = L < = R < N

Implementazione ingenua. O (N^3logn) complessità.

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

Supponiamo che per la gamma [L, R] sappiamo già ordinato serie A e invertire ordinato serie B. Quando ci sarà calcolare per la gamma [L, R + 1] esattamente un elemento sarà cancellato da B e inserito in A (questo numero è esattamente valori [R + 1]). C++ ha set di contenitori e multiset che ci permettono di inserire e rimuovere in tempo O (log) e iterare in tempo O (n). Anche altri linguaggi di programmazione hanno gli stessi contenitori (in java si tratta di TreeSet/SortedSet). Quindi, quando spostiamo R in R + 1, faremo alcune semplici query su multiset (inserire/rimuovere).

O (N^3) soluzione.

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

Answer 2

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