Как найти сумму минимальных элементов массива

Способ решения имеющий сложность 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("%lldn", sum_type_a);
    printf("%lldn", sum_type_b);
    printf("%lldn", 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

Данная тема основывается на теме: Массивы. Одномерные массивы. Инициализация массива

Содержание

• 1. Нахождение сумм и произведений элементов массива. Примеры
• 2. Нахождение максимального (минимального) элемента массива. Примеры
• 3. Сортировка массива методом вставки
• 4. Поиск элемента в массиве. Примеры
• Связанные темы

Поиск на других ресурсах:

1. Нахождение сумм и произведений элементов массива. Примеры

Пример 1. Задан массив A, содержащий 100 целых чисел. Найти сумму элементов этого массива. Фрагмент кода, решающего эту задачу

// сумма элементов массива A из 100 целых чисел
int A[100];
int suma; // переменная, содержащая сумму
int i;    // дополнительная переменная

// ввод массива A
// ...

// Вычисление суммы
suma = 0; // обнулить сумму
for (i=0; i<100; i++)
    suma += A[i];

Перебор всех элементов массива выполняется в цикле for.

Переменная sum сохраняет результирующее значение суммы элементов массива. Переменная i есть счетчиком, определяющим индекс элемента массива A[i].

Пример 2. Задан массив B, содержащий 20 вещественных чисел. Найти сумму элементов массива, которые лежат на парных позициях. Считать, что позиции 0, 2, 4 и т.д. есть парными.

// сумма элементов массива B
// лежащих на парных позициях
float B[20];
float sum; // переменная, содержащая сумму
int i; // дополнительная переменная

// ввод массива
// ...

// Вычисление суммы
sum = 0; // обнулить сумму
for (i=0; i<20; i++)
    if ((i%2)==0)
        sum += B[i];

В этом примере выражение

(i%2)==0

определяет парную позицию (парный индекс) массива B. Если нужно взять нечетные позиции, то нужно написать

(i%2)==1

Пример 3. Задан массив, который содержит 50 целых чисел. Найти сумму положительных элементов массива.

// сумма положительных элементов массива
int A[50];
int sum; // переменная, содержащая сумму
int i; // дополнительная переменная

// ввод массива
// ...

// Вычисление суммы
sum = 0; // обнулить сумму
for (i=0; i<50; i++)
    if (A[i]>0)
        sum = sum + A[i];

Пример 4. Задан массив из 50 целых чисел. Найти произведение элементов массива, которые есть нечетными числами.

// произведение нечетных элементов массива
int A[50];
int d; // переменная, содержащая произведение
int i; // вспомогательная переменная

// ввод массива
// ...

// Вычисление произведения
d = 1; // начальная установка переменной d
for (i=0; i<50; i++)
    if ((A[i]%2)==1)
        d = d * A[i];

Чтобы определить, есть ли элемент массива A[i] нечетным, нужно проверить условие

(A[i]%2)==1

Если условие выполняется, то элемент массива есть нечетное число.

⇑

2. Нахождение максимального (минимального) элемента массива. Примеры

Пример 1. Задан массив из 30 вещественных чисел. Найти элемент (индекс), имеющий максимальное значение в массиве.

// поиск позиции (индекса), содержащего максимальное значение
float B[30];
float max; // переменная, содержащая максимум
int index; // позиция элемента, содержащего максимальное значение
int i; // дополнительная переменная

// ввод массива
// ...

// поиск максимума
// установить максимум как 1-й элемент массива
index = 0;
max = B[0]; 
for (i=1; i<30; i++)
    if (max<B[i]) 
    { 
        max = B[i]; // запомнить максимум
        index = i;  // запомнить позицию максимального элемента
    }

В вышеприведенном примере переменная max содержит максимальное значение. Переменная index содержит позицию элемента, который имеет максимальное значение. В начале переменной max присваивается значение первого элемента массива. Затем, начиная со второго элемента, происходит прохождение всего массива в цикле for. Одновременно проверяется условие

if (max<B[i])

Если условие выполняется (найден другой максимум), тогда новое значение максимума фиксируется в переменных max и index.

Вышеприведенный пример находит только один максимум. Однако, в массивах может быть несколько максимальных значений. В этом случае для сохранения позиций (индексов) максимальных значений нужно использовать дополнительный массив как показано в следующем примере.

Пример 2. Задан массив содержащий 50 целых чисел. Найти позицию (позиции) элемента, который имеет минимальное значение. Если таких элементов несколько, сформировать дополнительный массив индексов.

// поиск позиций (индексов), содержащих минимальное значение
int A[50];
int min; // переменная, содержащая минимальное значение
int INDEXES[50]; // позиции элементов, содержащих минимальное значение
int n; // число одинаковых минимальных значений
int i; // дополнительная переменная


// ввод массива
// ...

// 1. Поиск минимального значения
// установить минимальное значение в первом элементе массива
min = A[0];
for (i=1; i<50; i++)
    if (min>A[i])
        min = A[i]; // запомнить минимальное значение

// 2. Формирование массива
n = 0; // обнулить счетчик в массиве INDEXES
for (i=0; i<50; i++)
    if (min == A[i])
        {
            n++; // увеличить число элементов в INDEXES
            INDEXES[n-1] = i; // запомнить позицию
        }

listBox1->Items->Clear();

// 3. Вывод массива INDEXES в listBox1
for (i=0; i<n; i++)     
    listBox1->Items->Add(INDEXES[i].ToString());

В вышеприведенном листинге сначала ищется минимальное значение min.

На втором шаге формируется массив INDEXES, в котором число элементов записывается в переменную n. Происходит поиск минимального значения в массиве A с одновременным формированием массива INDEXES.

На третьем шаге приведен пример, как вывести массив INDEXES в элементе управления listBox1(ListBox).

⇑

3. Сортировка массива методом вставки

Пример. Пусть дан массив A, содержащий 10 целых чисел. Отсортировать элементы массива в нисходящем порядке с помощью метода вставки.

// сортировка массива методом вставки
int A[10];
int i, j; // дополнительные переменные - счетчики
int t; // дополнительная переменная

// ввод массива A
// ...

// сортировка
for (i=0; i<9; i++)
    for (j=i; j>=0; j--)
        if (A[j]<A[j+1])
        {
            // поменять местами A[j] и A[j+1]
            t = A[j];
            A[j] = A[j+1];
            A[j+1] = t;
        }

⇑

4.  Поиск элемента в массиве. Примеры

Пример 1. Определить, находится ли число k в массиве M состоящем из 50 целых чисел.

// определение наличия заданного числа в массиве чисел
int M[50];
int i;
int k; // искомое значение
bool f_is; // результат поиска, true - число k есть в массиве, иначе false

// ввод массива M
// ...
// ввод числа k
// ...

// поиск числа в массиве
f_is = false;
for (i=0; i<50; i++)
    if (k==M[i])
    {
        f_is = true; // число найдено
        break; // выход из цикла, дальнейший поиск не имеет смысла
    }

// вывод результата
if (f_is)
    label1->Text = "Число " + k.ToString() + " есть в массиве M.";
else
    label1->Text = "Числа " + k.ToString() + " нет в массиве M.";

Пример 2. Найти все позиции вхождения числа k в массиве M состоящим из 50 целых чисел.

// определение всех позиций заданного числа в массиве чисел
int M[50]; // массив чисел
int i; // вспомогательная переменная
int k; // искомое значение
int INDEXES[50]; // искомый массив позиций вхождения числа k
int n; // количество найденных позиций или количество элементов в массиве INDEXES

// ввод массива M
// ...
// ввод числа k
// ...

// поиск числа k в массиве M и одновременное формирование массива INDEXES
n = 0;
for (i=0; i<50; i++)
    if (k==M[i])
    {
        // число найдено
        n++;
        INDEXES[n-1] = i;
    }

// вывод результата в listBox1
listBox1->Items->Clear();

for (i=0; i<n; i++)
    listBox1->Items->Add(INDEXES[i].ToString());

⇑

Связанные темы

• Массивы. Часть 1. Определение массива в C++. Одномерные массивы. Инициализация массива
• Массивы. Часть 2. Двумерные массивы. Массивы строк. Многомерные массивы

⇑