Сумма минимумов

Question

Дан массив ?, в котором содержится ? целых чисел. Нужно перебрать все пары чисел ?? и ?? в этом массиве, для каждой пары найти минимум min(??, ?? ) и сложить вместе все эти минимумы. Формат входных данных: В первой строке записано целое число ? — сколько чисел в массиве (1 <= ? <= 300 000). В остальных ? строках записаны сами эти числа в том порядке, в котором они идут в массиве ?. Все числа по модулю не превышают 10^9. Формат выходных данных: Нужно вывести одно целое число — искомую сумму минимумов ?. Сумма ? может быть довольно большой. Оценить максимально возможное значение ? и выбрать подходящий целочисленный тип. Требуется решить задачу за время ?(?). есть пока такая попытка, но это далеко не O(N):

#include<stdio.h>
int main(){
    int A[300001];
    int N;
    int S; 
    S = 0;
    scanf("%d\n", &N);
    for(int i=1; i<N; i++){
        scanf("%d\n", &A[i]);
    }
    for(int i=1; i<N; i++){
        for(int j=i+1; j!=i; j++){
            if(A[i,j]<=A[i,j+1])
                S=S+A[i,j];
            else
                S=S+A[i,j+1];
        }
    }
    printf("%d", S);
}

Answer 1

Способ решения имеющий сложность O(N * log(N)).

#include <stdio.h>
#include <stdlib.h>

int cmp(const void* a, const void* b)
{
    return *(int*)a - *(int*)b;
}

int main(void)
{
    static int A[300000];
    int N;

    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
        scanf("%d", &A[i]);

    qsort(A, N, sizeof(int), cmp);

    long long sum_elements = 0;
    long long sum_type_a = 0;
    long long sum_type_b = 0;
    long long sum_type_c = 0;
    for (int i = 0; i < N; ++i)
    {
        sum_type_a += (long long)A[i] * (N - 1 - i);
        sum_type_b += (long long)A[i] * (N - 1 - i) + A[i];
        sum_type_c += (long long)A[i] * (N - 1 - i) + A[i] + sum_elements;
        sum_elements += A[i];
    }

    printf("%lld\n", sum_type_a);
    printf("%lld\n", sum_type_b);
    printf("%lld\n", sum_type_c);
}

Тут выводится три суммы.
Первая сумма считается в предположении, что если мы учли пару (A[i], A[j]), то пару (A[j], A[i]) учитывать не нужно. Также первая сумма не учитывает пары вида (A[i], A[i]).
Вторая сумма аналогична первой, но учитывает пары вида (A[i], A[i]).
Третья сумма аналогична второй, но учитывает обе пары (A[i], A[j]) и (A[j], A[i]).
Не знаю, какую именно сумму вам нужно найти...

На входных данных

5
1 2 3 4 5

Будет следующий вывод:

20
35
55

БЛОГ НА HUSL

Сумма минимумов

Ответы (1 шт):