tổng tiếp giáp tối thiểu có thể đạt được bằng cách thực hiện nhiều nhất là K hoán đổi

Question

Tôi có bài tập về nhà này:

Với một mảng gồm N số nguyên, bạn được yêu cầu để in tổng tiếp giáp tối thiểu có thể đạt được bằng cách thực hiện tối đa K giao dịch hoán đổi. Trong quá trình hoán đổi, bất kỳ 2 phần tử nào của mảng đã cho có thể được hoán đổi.

Tôi cố gắng này

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

Nó sẽ cho tổng tối thiểu mà không cần bất kỳ swappings, nhưng làm thế nào tôi có thể cải thiện trong không quá K giao dịch hoán đổi?

Answer 1

Giải pháp của bạn không chính xác ngay cả khi không trao đổi.

Kiểm tra: [-1, 2, -1]. Câu trả lời của bạn về bài kiểm tra này là -2. Câu trả lời đúng: -1

Tôi hy vọng giải pháp của tôi không tốt nhất và có cách tiếp cận tốt hơn.

Giải pháp phức tạp O (N^3) đơn giản.

Giả sử rằng tối thiểu phân khúc tiếp giáp thức của chúng tôi sẽ là [L, R] đối với một số 0 < = L < = R < N. Bây giờ chúng ta có hai MultiSet: A và B. A - MultiSet với những con số "bên trong" (các số nằm trong phạm vi [L, R]) và B - bội số với các số "bên ngoài" (các số nằm ngoài phạm vi [L, R]). Ra mục tiêu là để giảm thiểu tổng số trong A - sum (A). Việc hoán đổi bên trong A hoặc B là có ý nghĩa, bởi vì nó sẽ không ảnh hưởng đến tổng (A). Chúng ta có thể hoán đổi một phần tử từ A với phần tử khác trong B. Chúng ta không có nhiều hơn K hoán đổi, và nó có nghĩa là không quá K phần tử trong A sẽ được hoán đổi không quá K thành phần trong B. Để đạt được giá trị tối thiểu của tổng (A) chúng tôi sẽ lấy một số yếu tố tối đa trong A và trao đổi chúng với các yếu tố tối thiểu trong B. Ví dụ:

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

• Chúng tôi có thể thực hiện 0 hoán đổi, A = {-3, -3, -1, 2}; B = {-4, 1, 3, 6}; sau đó tổng hợp (A) == -3
• Chúng tôi có thể thực hiện 1 lần hoán đổi, A = {-3, -3, -1, -4}; B = {2, 1, 3, 6}; sau đó tổng hợp (A) == -11
• Chúng tôi có thể thực hiện 2 lần hoán đổi, A = {-3, -3, 1, -4}; B = {2, -1, 3, 6}; sau đó sum (A) == -9

trả lời là sum (A) == -11

Đối với phạm vi [L, R] chúng tôi có thể nhận được số tiền tối thiểu có thể. Để có được câu trả lời cho vấn đề ban đầu của chúng tôi, chúng tôi sẽ lặp qua tất cả các phạm vi có thể có [L, R]. 0 < = L < = R < N

Thực hiện Naive. O (N^3logn) phức tạp.

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

Tối ưu hóa

Giả sử rằng trong phạm vi [L, R] chúng ta đã biết sắp xếp tập A và đảo ngược được sắp xếp bộ B. Khi chúng tôi sẽ tính toán trong phạm vi [L, R + 1] chính xác một phần tử sẽ bị xóa khỏi B và được chèn vào A (số này chính xác là giá trị [R + 1]). C++ có các bộ chứa và bộ đa có thể cho phép chúng ta chèn và loại bỏ trong thời gian O (log) và lặp lại trong thời gian O (n). Các ngôn ngữ lập trình khác cũng có các thùng chứa giống nhau (trong java nó là TreeSet/SortedSet). Vì vậy, khi chúng ta di chuyển R sang R + 1, chúng ta sẽ thực hiện một số truy vấn đơn giản với multiset (insert/remove).

O (N^3) giải pháp.

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