Задача 38: Конфуз (XV Всеукраинская
олимпиада по информатике)
Пусть A - массив, состоящий из N элементов A1,...,AN. Обозначим его
максимальное и минимальное значение как max(A) и min(A)
соответственно. Вычислим сумму элементов S, S = A1 + A2 + ... + AN.
Заменим каждый элемент массива на разницу S и этого элемента: Ai :=
S - Ai, 1 < i < N. Такое преобразование массива A назовем операцией
Confuse.
Задание
Напишите программу CONFUSE, которая по массиву B, полученному в
результате K-кратного применения операции Confuse к некоторому
массиву A, вычислит разность max(A)-min(A).
Входные данные
Первая строка входного файла CONFUSE.DAT содержит целые числа N
и K, где N - количество элементов массива B (2 < N < 10000), а K -
количество применений операции Confuse к начальному массиву A, 1 < K
< 100. Вторая строка файла содержит N элементов массива B. Элементы
массива B - целые числа, принадлежащие диапазону от -2 000 000 000
до 2 000 000 000.
Выходные данные
Единственная строка выходного файла CONFUSE.SOL должна содержать
целое число, которое есть разностью max(A) и min(A).
Пример входных данных
4 2
45 52 47 46
Пример выходных данных
7
Решение:
Пусть x - начальный массив. Сумма его элементов - S. Пусть y -
массив, который получаем после преобразования, тогда S - max(x) =
min(y), т.к. отнимая от константы наибольшое значение из возможных
получаем наименьшее. Следовательно max(y) = S - min(x). Остальные
значения массива y будут лежать в пределах от min(y) до max(y).
Найдем разницу max(y) - min(y) = S - min(x) - S + max(x) = max(x) -
min(x). Применяя эту операцию K раз получим, что max(y) - min(y) =
max(a) - min(a). Т.е. нам достаточно найти наибольший и наименьший
элемент массива, а затем найти их разность.
Временная сложность этого алгоритма O(n). Нам достаточно одного
прохода по массиву. Необходимо завести две переменных min и max и
первоначально инициализировать их первым элементом массива. Затем,
если очередной элемент массива больше max, то заменяем значение max
на его значение, точно также для min.
Далее
ð
