Minimum zusammenhängende Summe, die durch die Durchführung höchstens erhalten werden kann K Swaps

Question

Ich habe diese Hausaufgaben:

ein Array bestehend aus N ganzen Zahlen gegeben, Sie sind erforderlich, um die minimale sequenzielle Summe zu drucken, die durch die Durchführung erhalten werden kann höchstens K Swaps. Während eines Tauschs könnten 2 Elemente des gegebenen Arrays ausgetauscht werden.

ich versucht, dieses

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

Es wird die Mindestsumme ohne Auslagerungen geben, aber wie kann ich in nicht mehr als K Swaps verbessern?

Answer 1

Ihre Lösung ist auch ohne Swap nicht korrekt.

Test: [-1, 2, -1]. Ihre Antwort auf diesen Test ist -2. Richtige Antwort: -1

Ich hoffe, dass meine Lösung nicht die beste ist und es gibt einen besseren Ansatz.

Einfache O (N^3) Komplexitätslösung.

Nehmen wir an, dass unser endgültiges minimalen sequenziellen Segment wird [L, R] für einige 0 < = L < = R < N. Jetzt haben wir zwei multiset: A und B. A - multiset mit "inneren" Zahlen (Zahlen innerhalb des Bereichs [L, R]) und B - Multiset mit "äußeren" Zahlen (Zahlen außerhalb des Bereichs [L, R]). Ziel ist es, die Summe der Zahlen in A - Summe (A) zu minimieren. Swaping in A oder B ist sinnvoll, da es sich nicht auf die Summe (A) auswirkt. Wir können ein Element von A mit einem anderen Element in B austauschen. Wir haben nicht mehr als K Swaps und es bedeutet, dass nicht mehr als K Elemente in A mit nicht mehr als K Elementen in B getauscht werden. Um den Minimalwert der Summe zu erreichen (A) Wir nehmen einige maximale Elemente in A und tauschen sie mit minimalen Elementen in B aus. Zum Beispiel:

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

• Wir können 0 tauschen, A = {-3, -3, -1, 2}; B = {-4, 1, 3, 6}; dann sum (A) == -3
• Wir können 1 Tauschen machen, A = {-3, -3, -1, -4}; B = {2, 1, 3, 6}; dann sum (A) == -11
• Wir können 2 Tauschen machen, A = {-3, -3, 1, -4}; B = {2, -1, 3, 6}; Summe (A) dann == -9

Antwort ist die Summe (A) == -11

Für Bereich [L, R] können wir minimal mögliche Summe bekommen. Um eine Antwort für unser anfängliches Problem zu erhalten, werden wir über alle möglichen Bereiche iterieren [L, R]. 0 < = L < =

Naive Implementierung. O (N^3logn) Komplexität.

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

Optimierung

Lassen Sie uns davon ausgehen, dass für den Bereich [L, R] wissen wir bereits sortierte Menge A und Reverse B. sortierte Menge, wenn wir für den Bereich berechnen wird [L, R + 1] genau ein Element wird von B gelöscht und in A eingefügt (diese Zahl ist genau die Werte [R + 1]). C++ hat Container-Set und Multiset, die es uns erlauben, in O (Log) -Zeit einzufügen und zu entfernen und in O (n) -Zeit zu iterieren. Andere Programmiersprachen haben auch dieselben Container (in Java ist es TreeSet/SortedSet). Wenn wir also R nach R + 1 verschieben, werden wir einige einfache Anfragen an multiset (insert/remove) stellen.

O (N^3) -Lösung.

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