Döyüş mühafizəsi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Akkolit Amazon
Geyim Geri qayıtmaBaxılıb 621

Problem bəyanat

Dartma problemində bir array tam ədədi, dizini hər iki böyüklüyün iki alt hissəsinə bölün ki, iki alt cəmin fərqi mümkün qədər minimum olsun. N hətta hər alt dəstin ölçüsü n / 2-dir. N tək olduqda bir alt dəstin ölçüsü n-2/1, digərinin ölçüsü n + 2/1 olmalıdır. Hər iki alt elementin cəmi təxminən eyni cəm olmalıdır.

Giriş Formatı

Bir tam ədədi olan ilk və yalnız bir sətir.

N boşluqla ayrılmış tam ədədi olan ikinci sətir.

Çıxış formatı

N-1 elementi olan alt-qrupu ehtiva edən birinci sətir, n hətta əks halda n-2/1 elementlərinə malikdirsə.

N + 2 elementə sahib olan alt sətri ehtiva edən ikinci sətir, n hətta əks halda n + 2/1 elementə malikdirsə.

Məhdudiyyətlər

  • 1 <= N <= 10 ^ 3
  • -10 ^ 5 <= a [i] <= 10 ^ 5

misal

10
1 4 7 -3 15 11 14 13 10 8
4 7 8 11 13
10 14 6 15 -3

Explanation: Burada ölçü hər bir massivin uzunluğu 10-a bərabərdir (5). (4 + 7 + 8 + 11 + 13) - (10 + 14 + 6 + 15 + -3) = 0, minimum fərq.

9
-1 -3 -5 -6 4 17 23 27 19
-5 4 11 23 
-1 -3 -6 17 27

Explanation: Burada ölçü 9 (tək), bir sıra ölçüsü 5, digəri isə 4 olacaq. (23 + 11 + 4 + -5) - (27 + 17 + -6 + -3 + -1) = -1

Dartma müharibəsi alqoritmi

Yarım ölçünün hər alt hissəsini sınayın və qalan yarısı ilə müqayisə edin.

a. Mövcud dəsti boş bir dəst olaraq işə salırıq və elementləri bir-bir əlavə edirik.

b. Bütün elementlər üçün cari dəstin bir hissəsi və ya qalan dəstin bir hissəsi olmalıdır.

c. Mövcud set n / 2 olduqda, bu həll nöqtəsinin o vaxta qədər mövcud olan ən yaxşı həll variantından daha yaxşı olub olmadığını yoxlayırıq.

d. Ən yaxşı həlldirsə yeniləyin. Son həlli çap edin.

Həyata keçirilməsi

C ++ Dartma Döyüş Proqramı

#include <iostream>
#include <stdlib.h>
#include <limits.h>
using namespace std;
 
void TugofWarRecur(int* array, int n, bool* current_elements, int selected_elements_count,bool* solution, int* min_diff, int sum, int current_sum, int current_position)
{
    
    if (current_position == n)
    {
        return;
    }
    if ((n/2 - selected_elements_count) > (n - current_position))
    {
        return;
    }
 
    TugofWarRecur(array, n, current_elements, selected_elements_count,solution, min_diff, sum, current_sum, current_position+1);
 
    selected_elements_count++;
    current_sum = current_sum + array[current_position];
    current_elements[current_position] = true;
    if (selected_elements_count == n/2)
    {
        if (abs(sum/2 - current_sum) < *min_diff)
        {
            *min_diff = abs(sum/2 - current_sum);
            for (int i = 0; i<n; i++)
            {
                solution[i] = current_elements[i];
            }
        }
    }
    else
    {
        TugofWarRecur(array, n, current_elements, selected_elements_count, solution, min_diff, sum, current_sum, current_position+1);
    }
    current_elements[current_position] = false;
}
 
void TugOfWar(int *array, int n)
{
    bool* current_elements = new bool[n];
    bool* solution = new bool[n];
    int min_diff = INT_MAX;
    int sum = 0;
    for (int i=0; i<n; i++)
    {
        sum =sum + array[i];
        current_elements[i] =  solution[i] = false;
    }
    TugofWarRecur(array, n, current_elements, 0, solution, &min_diff, sum, 0, 0);
    for (int i=0; i<n; i++)
    {
        if(solution[i] == true)
        {
            cout << array[i] << " ";
        }
    }
    cout<<endl;
    for (int i=0; i<n; i++)
    {
        if(solution[i] == false)
        {
            cout << array[i] << " ";
        }
    }
}
 
//Main function
int main()
{
    int n;
    cin>>n;
    int input_array[n];
    for(int i=0;i<n;i++)
    {
        cin>>input_array[i];
    }
    TugOfWar(input_array,n);
    return 0;
}

Java Proqramı

import java.util.Scanner;
class sum
{
    public static void TOWUtil(int arr[], int n, boolean curr_elements[], int no_of_selected_elements, boolean soln[], int sum, int curr_sum, int curr_position, int min_diff) 
    { 
        if (curr_position == n) 
            return; 
        if ((n / 2 - no_of_selected_elements) > (n - curr_position)) 
            return; 
        TOWUtil(arr, n, curr_elements,no_of_selected_elements, soln, sum, curr_sum, curr_position+1, min_diff); 
        no_of_selected_elements++; 
        curr_sum = curr_sum + arr[curr_position]; 
        curr_elements[curr_position] = true; 
        if (no_of_selected_elements == n / 2) 
        { 
            if (Math.abs(sum / 2 - curr_sum) < min_diff) 
            { 
                min_diff = Math.abs(sum / 2 - curr_sum); 
                for (int i = 0; i < n; i++) 
                    soln[i] = curr_elements[i]; 
            } 
        } 
        else
        { 
            TOWUtil(arr, n, curr_elements,no_of_selected_elements,soln, sum, curr_sum,curr_position + 1, min_diff); 
        } 
        curr_elements[curr_position] = false; 
    } 
    public static void solve(int arr[]) 
    { 
        int n = arr.length;
        boolean[] curr_elements = new boolean[n]; 
        boolean[] soln = new boolean[n]; 
        int min_diff = Integer.MAX_VALUE; 
        int sum = 0; 
        for (int i = 0; i < n; i++) 
        { 
            sum += arr[i]; 
            curr_elements[i] = soln[i] = false; 
        } 
        TOWUtil(arr, n, curr_elements, 0,soln, sum, 0, 0, min_diff); 
        for (int i = 0; i < n; i++) 
        { 
            if (soln[i] == true) 
                System.out.print(arr[i] + " "); 
        } 
        System.out.println(); 
        for (int i = 0; i < n; i++) 
        { 
            if (soln[i] == false) 
                System.out.print(arr[i] + " "); 
        }
        System.out.println();
    } 
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int input_array[] = new int [n];
        for(int i=0;i<n;i++)
        {
            input_array[i] = sr.nextInt();
        }
        solve(input_array);
    }
}
6
9 6 4 2 7 -2
9 6 4 
2 7 -2

Dartan Döyüşünün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n ^ 2) burada n - massivdə mövcud olan elementlərin sayı. N alt dəstinin ölçüsü cütdürsə, n / 2-yə bölünməlidir, lakin n-nin tək dəyəri üçün bir alt dəstin ölçüsü (n-1) / 2, başqa bir altın ölçüsü olmalıdır. (n + 1) / 2.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.

References

Translate »